Rainbow Colouring of Split and Threshold Graphs

DOI10.1007/978-3-642-32241-9_16zbMath1364.68223arXiv1205.1670OpenAlexW2962868340MaRDI QIDQ2914323

Deepak Rajendraprasad, L. Sunil Chandran

Publication date: 25 September 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

complexityapproximationchordal graphssplit graphsdegree sequencerainbow connectivitythreshold graphsrainbow colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

On the Fine-Grained Complexity of Rainbow Coloring ⋮ On the complexity of rainbow coloring problems ⋮ Rainbow colouring of split graphs ⋮ Rainbow connection number and graph operations ⋮ Rainbow tetrahedra in Cayley graphs ⋮ Rainbow connections of graphs: a survey ⋮ A survey on rainbow (vertex-)index of graphs ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Fine-grained complexity of rainbow coloring and its variants ⋮ Fine-Grained Complexity of Rainbow Coloring and its Variants. ⋮ Rainbow connectivity and rainbow criticality on graph classes

This page was built for publication: Rainbow Colouring of Split and Threshold Graphs