Rainbow colouring of split graphs

DOI10.1016/J.DAM.2015.05.021zbMath1350.05029arXiv1404.4478OpenAlexW1490942642MaRDI QIDQ344835

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 graphthreshold graphrainbow connectivityrainbow colouring

Mathematics Subject Classification ID

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

Related Items (4)

On the Fine-Grained Complexity of Rainbow Coloring ⋮ A survey on rainbow (vertex-)index of graphs ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Vertex deletion on split graphs: beyond 4-hitting set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rainbow-\(k\)-connectivity of random graphs
• Rainbow connection number of graph power and graph products
• Hardness and algorithms for rainbow connection
• Rainbow connection number and radius
• On rainbow connection
• The splittance of a graph
• Rainbow connections of graphs: a survey
• Rainbow connection number and connected dominating sets
• New Hardness Results in Rainbow Connectivity
• Rainbow Colouring of Split and Threshold Graphs
• Inapproximability of Rainbow Colouring
• Rainbow connection in graphs
• Rainbow Connection in Graphs with Minimum Degree Three
• The complexity of theorem-proving procedures

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