  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.
