Rainbow colouring of split graphs

DOI10.1016/J.DAM.2015.05.021zbMATH Open1350.05029arXiv1404.4478OpenAlexW1490942642MaRDI QIDQ344835FDOQ344835

L. Sunil Chandran, Deepak Rajendraprasad, Marek Tesař

Publication date: 24 November 2016

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

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.

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

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

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)

Cites Work

• On rainbow connection
• Rainbow connections of graphs: a survey
• Rainbow connection number and connected dominating sets
• Rainbow connection in graphs
• Hardness and algorithms for rainbow connection
• The complexity of theorem-proving procedures
• Rainbow Connection in Graphs with Minimum Degree Three
• The splittance of a graph
• Chromatic graph theory
• Rainbow connectivity: hardness and tractability
• Rainbow connection number and radius
• Rainbow Colouring of Split and Threshold Graphs
• Inapproximability of Rainbow Colouring
• Title not available (Why is that?)
• Title not available (Why is that?)
• On rainbow-\(k\)-connectivity of random graphs
• Rainbow connection number of graph power and graph products

Cited In (8)

• On the Fine-Grained Complexity of Rainbow Coloring
• Rainbow Colouring of Split and Threshold Graphs
• Rainbow degree-jump coloring of graphs
• Title not available (Why is that?)
• Vertex deletion on split graphs: beyond 4-hitting set
• On colorings of split graphs
• Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs
• A survey on rainbow (vertex-)index of graphs

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)