Upper bounding rainbow connection number by forest number
- 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).& nbsp;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.& nbsp;In this work we show that if we consider the forest number f(G), the numberA 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).& nbsp;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.& nbsp;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.…
Author details: | Sunil L. Chandran, Davis Issac, Juho LauriORCiD, Erik Jan van Leeuwen |
---|---|
DOI: | https://doi.org/10.1016/j.disc.2022.112829 |
ISSN: | 0012-365X |
ISSN: | 1872-681X |
Title of parent work (English): | Discrete mathematics |
Publisher: | Elsevier |
Place of publishing: | Amsterdam [u.a.] |
Publication type: | Article |
Language: | English |
Date of first publication: | 2022/03/01 |
Publication year: | 2022 |
Release date: | 2024/03/21 |
Tag: | forest number; rainbow connection; upper bound |
Volume: | 345 |
Issue: | 7 |
Article number: | 112829 |
Number of pages: | 22 |
Funding institution: | Alexander von Humboldt Foundation fellowship |
Organizational units: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC classification: | 5 Naturwissenschaften und Mathematik / 50 Naturwissenschaften / 500 Naturwissenschaften und Mathematik |
Peer review: | Referiert |
License (German): | Keine öffentliche Lizenz: Unter Urheberrechtsschutz |