论文标题

上边界彩虹连接编号按森林编号

Upper Bounding Rainbow Connection Number by Forest Number

论文作者

Chandran, L. Sunil, Issac, Davis, Lauri, Juho, van Leeuwen, Erik Jan

论文摘要

如果没有两个边缘的颜色相同,则彩虹中的一条路径是彩虹,如果每对顶点之间都有彩虹路径,则该图是彩虹相连的。彩虹连接所需的最小颜色数量$ g $是$ g $的彩虹连接数,由$ \ text {rc}(g)$表示。 彩虹连接图$ g $的一种简单方法是为带有不同颜色的跨越树的边缘上色,然后重复使用这些颜色中的任何一种,以使其余的边缘为$ g $。这证明了$ \ text {rc}(g)\ le | v(g)| -1 $。我们询问类似树状的结构和彩虹色之间是否比上述琐碎的论点暗示了更强的联系。例如,是否可以找到$ t(g)-1 $的上限,对于$ \ text {rc}(g)$,其中$ t(g)$是$ g $的最大诱导树中的顶点数?答案被证明是负面的,因为有反例表明即使$ c \ cdot t(g)$也不是任何给定常量$ c $的$ \ text {rc}(g))$的上限。 在这项工作中,我们表明,如果我们考虑森林数字$ f(g)$,最大诱发森林中的顶点数量,而不是$ t(g)$,那么令人惊讶的是,我们确实获得了上限。更具体地说,我们证明$ \ text {rc}(g)\ leq f(g) + 2 $。我们的结果表明,彩虹连接和类似树状的结构之间的联系比简单的基于树的上限所建议的。

A path in an edge-colored graph is rainbow if no two edges of it are colored the same, and the graph is rainbow-connected if there is a rainbow path between each pair of its vertices. The minimum number of colors needed to rainbow-connect a graph $G$ is the rainbow connection number of $G$, denoted by $\text{rc}(G)$. A simple way to rainbow-connect a graph $G$ is to color the edges of a spanning tree with distinct colors and then re-use any of these colors to color the remaining edges of $G$. This proves that $\text{rc}(G) \le |V(G)|-1$. We ask whether there is a stronger connection between tree-like structures and rainbow coloring than that is implied by the above trivial argument. For instance, is it possible to find an upper bound of $t(G) -1$ for $\text{rc}(G)$, where $t(G)$ is the number of vertices in the largest induced tree of $G$? The answer turns out to be negative, as there are counter-examples that show that even $c\cdot t(G)$ is not an upper bound for $\text{rc}(G))$ for any given constant $c$. In this work we show that if we consider the forest number $f(G)$, the number of vertices in a maximum induced forest of $G$, instead of $t(G)$, then surprisingly we do get an upper bound. More specifically, we prove that $\text{rc}(G) \leq f(G) + 2$. Our result indicates a stronger connection between rainbow connection and tree-like structures than that was suggested by the simple spanning tree based upper bound.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源