Back to Search
Start Over
Upper bounding rainbow connection number by forest number.
- Source :
-
Discrete Mathematics . Jul2022, Vol. 345 Issue 7, pN.PAG-N.PAG. 1p. - Publication Year :
- 2022
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *RAINBOWS
*SPANNING trees
*CHARTS, diagrams, etc.
*GRAPH coloring
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 345
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 156843461
- Full Text :
- https://doi.org/10.1016/j.disc.2022.112829