A rainbow path in an edge coloured graph is a path in which no two edges are coloured the same. A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one rainbow path. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Between them, Chakraborty et al. [J. Comb. Optim., 2011] and Ananth et al. [FSTTCS, 2012] have shown that for every integer k, k \geq 2, it is NP-complete to decide whether a given graph can be rainbow coloured using k colours. A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. Chandran and Rajendraprasad have shown that the problem of deciding whether a given split graph G can be rainbow coloured using 3 colours is NP-complete and further have described a linear time algorithm to rainbow colour any split graph using at most one colour more than the optimum [COCOON, 2012]. In this article, we settle the computational complexity of the problem on split graphs and thereby discover an interesting dichotomy. Specifically, we show that the problem of deciding whether a given split graph can be rainbow coloured using k colours is NP-complete for k \in {2,3}, but can be solved in polynomial time for all other values of k.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok