Rainbow Colouring of Split and Threshold Graphs
From MaRDI portal
Publication:2914323
DOI10.1007/978-3-642-32241-9_16zbMath1364.68223arXiv1205.1670MaRDI 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
complexityapproximationchordal graphssplit graphsdegree sequencerainbow connectivitythreshold graphsrainbow colouring
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs, Fine-Grained Complexity of Rainbow Coloring and its Variants., A survey on rainbow (vertex-)index of graphs, Rainbow colouring of split graphs, Rainbow tetrahedra in Cayley graphs, On the complexity of rainbow coloring problems, Rainbow connections of graphs: a survey, Fine-grained complexity of rainbow coloring and its variants, Rainbow connectivity and rainbow criticality on graph classes, Rainbow connection number and graph operations, On the Fine-Grained Complexity of Rainbow Coloring