Upper bounding rainbow connection number by forest number

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

e x t r c (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

e x t r c (G) l e | 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

e x t r c (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 c d o t t (G)

is not an upper bound for

e x t r c (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

e x t r c (G) l e q 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.

Review text

A path in a (not necessarily proper) edge-colouring of a graph is said to be rainbow if no two edges in it are the same colour, and a graph is rainbow-connected if there is a rainbow path between any two vertices of the graph. The rainbow connection number \(\text{rc}(G)\) of a graph \(G\) is the smallest number of colours needed to produce a rainbow-connected colouring of \(G\). An obvious upper bound is \(\text{rc}(G)\leq \vert V(G)\vert -1\) obtained by taking a spanning tree of \(G\) and giving each of its \(\vert V(G)\vert -1\) edges a different colour. As this bound feels quite crude, one might ask if, for example, it is possible to bound \(\text{rc}(G)\) above by other parameters related to the tree and forest structure of the graph. The main result of the paper is that if we define the forest number \(f(G)\) of a graph to be the number of vertices in the largest induced forest in the graph, then \(\text{rc}(G)\leq f(G)+2\). This is within an additive constant 3 of best possible as trees have \(\text{rc}(G)=\vert V(G)\vert - 1=f(G)-1\). Determination of the best result is left as an open problem. For a little insight into the proof, the authors fix a maximum induced forest in \(G\) and contract each component of that forest to a single vertex. Call the resulting graph \(H\), it has tree vertices (from the contracted trees) and non-tree vertices. A judiciously chosen spanning tree of \(H\) is then chosen. The idea is now to use a small number of surplus colours to finish off the colouring after colouring the maximum forest with \(f(G)-1\) colours, though technical issues arise with this.

Recommendations

Cites work

Cited in

(2)

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)