Upper bounding rainbow connection number by forest number (Q2138952): Difference between revisions

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.