NP-completeness of a family of graph-colouring problems

DOI10.1016/0166-218X(83)90020-3zbMath0504.05032MaRDI QIDQ1835680

Robert W. Irving

Publication date: 1983

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

zbMATH Keywords

NP-completegraph colourability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

On the complexity of H-coloring ⋮ The complexity of multicolouring ⋮ Vertex coloring of a graph for memory constrained scenarios ⋮ Exact and Parameterized Algorithms for (k, i)-Coloring ⋮ Unnamed Item ⋮ On the tractability of \(( k , i )\)-coloring

Cites Work

• Unnamed Item
• Kneser's conjecture, chromatic number, and homotopy
• n-tuple colorings and associated graphs
• r-tuple colorings of uniquely colorable graphs
• Some simplified NP-complete graph problems
• Set colourings of graphs
• The footballers of Croam
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The Complexity of Near-Optimal Graph Coloring
• A (<5)-Colour Theorem for Planar Graphs
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS

This page was built for publication: NP-completeness of a family of graph-colouring problems