Rainbow colouring of split graphs

• Published in: Discrete Applied Mathematics 2017-01, Vol.216, p.98-113
• Main Authors: Chandran, L. Sunil, Rajendraprasad, Deepak, Tesař, Marek
• Format: Article
• Language: English
• Subjects: Applied mathematics; Color; Coloring; Combinatorics; Complexity; Graph theory; Graphs; Optimization; Polynomials; Rainbow colouring; Rainbow connectivity; Split graph; Threshold graph
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2015.05.021

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. It is known that, unless P=NP, the rainbow connection number of a graph cannot be approximated in polynomial time to a multiplicative factor less than 5/4, even when the input graph is chordal [Chandran and Rajendraprasad, FSTTCS 2013]. In this article, we determine the computational complexity of the above problem on successively more restricted graph classes, viz.: split graphs and threshold graphs. In particular, we establish the following: 1.The problem of deciding whether a given split graph can be rainbow coloured using k colours is NP-complete for k∈{2,3}, but can be solved in polynomial time for all other values of k. Furthermore, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum.2.For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Furthermore, we can optimally rainbow colour a threshold graph in linear time.