TY - JOUR

T1 - Upper bounding rainbow connection number by forest number.

AU - Chandran, L. Sunil

AU - Issac, Davis

AU - Lauri, Juho

AU - Leeuwen, Erik Jan van

N1 - Funding Information:
The major part of the work was done when this author was on a long-term research visit at Max Planck Institute for Informatics, Saarbrücken, Germany. The visit was funded by the Alexander von Humboldt Foundation fellowship.
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2022/7

Y1 - 2022/7

N2 - 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 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 rc(G)≤|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 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⋅t(G) is not an upper bound for 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 rc(G)≤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.

AB - 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 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 rc(G)≤|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 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⋅t(G) is not an upper bound for 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 rc(G)≤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.

KW - Forest number

KW - Rainbow connection

KW - Upper bound

UR - http://www.scopus.com/inward/record.url?scp=85125457048&partnerID=8YFLogxK

U2 - 10.1016/J.DISC.2022.112829

DO - 10.1016/J.DISC.2022.112829

M3 - Article

SN - 0012-365X

VL - 345

SP - 112829

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 7

M1 - 112829

ER -