Rainbow colouring of split graphs

DOI10.1016/J.DAM.2015.05.021MaRDI QIDQ344835zbMATH OpenOpenAlexFDO

Authors L. Sunil Chandran, Deepak Rajendraprasad, Marek Tesař

Publication date 24 November 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.4478

zbMATH Keywords

complexitysplit graphrainbow connectivitythreshold graphrainbow colouring

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: 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.

Recommendations

• Rainbow Colouring of Split and Threshold Graphs
• Computing minimum rainbow and strong rainbow colorings of block graphs
• Inapproximability of Rainbow Colouring
• Rainbow graph splitting
• Rainbow connectivity: hardness and tractability

Cites work

• A sharp threshold for rainbow connection of random bipartite graphs
• Chromatic graph theory
• Hardness and algorithms for rainbow connection
• Inapproximability of Rainbow Colouring
• On rainbow connection
• On rainbow-\(k\)-connectivity of random graphs
• Rainbow Colouring of Split and Threshold Graphs
• Rainbow connection in graphs
• Rainbow connection in graphs with minimum degree three
• Rainbow connection number and connected dominating sets
• Rainbow connection number and radius
• Rainbow connection number of graph power and graph products
• Rainbow connection numbers of line graphs.
• Rainbow connectivity: hardness and tractability
• The complexity of theorem-proving procedures
• The splittance of a graph

Cited in

(10)

• Rainbow Colouring of Split and Threshold Graphs
• scientific article; zbMATH DE number 7219311 (Why is no real title available?)
• On colorings of split graphs
• Computing minimum rainbow and strong rainbow colorings of block graphs
• Rainbow degree-jump coloring of graphs
• Rainbow graph splitting
• On the fine-grained complexity of rainbow coloring
• Rainbow vertex coloring bipartite graphs and chordal graphs
• A survey on rainbow (vertex-)index of graphs
• Vertex deletion on split graphs: beyond 4-hitting set

This page was built for publication: Rainbow colouring of split graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344835)