Upper bounding rainbow connection number by forest number

DOI10.1016/J.DISC.2022.112829MaRDI QIDQ2138952zbMATH OpenOpenAlexFDO

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

Publication date 17 May 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

upper boundrainbow connectionforest number

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cites work

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

Cited in

(1)

• Total-rainbow connection and forbidden subgraphs

Describes a project that uses

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)