Rainbow colouring of split graphs

详细信息    查看全文

• 作者：L. Sunil Chandran^a ; ^{sunil@csa.iisc.ernet.in} ; Deepak Rajendraprasad^b ; ^{deepakmail@gmail.com} ; Marek Tesař^c ; ^{tesar@kam.mff.cuni.cz}
• 关键词：Rainbow connectivity ; Rainbow colouring ; Split graph ; Threshold graph ; Complexity
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：98-113
• 全文大小：605 K
• 卷排序：216

文摘

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 GG is a colouring of the edges of GG such that every pair of vertices in GG is connected by at least one rainbow path. The minimum number of colours required to rainbow colour GG 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/45/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 kk colours is NP-complete for k∈{2,3}k∈{2,3}, but can be solved in polynomial time for all other values of kk. 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 kk, threshold graphs with rainbow connection number kk can be characterised based on their degree sequence alone. Furthermore, we can optimally rainbow colour a threshold graph in linear time.