Upper bounding rainbow connection number by forest number

DOI10.1016/J.DISC.2022.112829zbMATH Open1490.05067arXiv2006.06551OpenAlexW4214717099MaRDI QIDQ2138952FDOQ2138952

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

Publication date: 17 May 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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 $extrc(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 $extrc(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 $extrc(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 $ccdott(G)$ is not an upper bound for $extrc(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 $extrc(G)leqf(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.

Full work available at URL: https://arxiv.org/abs/2006.06551

Recommendations

• Bounds for the rainbow connection number of graphs
• Rainbow connection and forbidden subgraphs
• Rainbow connection and minimum degree
• scientific article
• The rainbow connection number of 2-connected graphs

zbMATH Keywords

upper boundrainbow connectionforest number

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Cites Work

• On rainbow connection
• Rainbow connections of graphs: a survey
• Rainbow connection number and connected dominating sets
• Rainbow connection in graphs
• Hardness and algorithms for rainbow connection
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Facet defining inequalities among graph invariants: The system graphedron
• The rainbow connection number of 2-connected graphs
• Rainbow connection number and radius
• Some remarks on rainbow connectivity
• Rainbow connection in oriented graphs

Cited In (1)

• Total-rainbow connection and forbidden subgraphs

Uses Software

• GraPHedron

This page was built for publication: Upper bounding rainbow connection number by forest number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138952)