NP-completeness of a family of graph-colouring problems

DOI10.1016/0166-218X(83)90020-3zbMATH Open0504.05032MaRDI QIDQ1835680FDOQ1835680

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)

Cites Work

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

Cited In (6)

• Exact and Parameterized Algorithms for (k, i)-Coloring
• The complexity of multicolouring
• On the tractability of \(( k , i )\)-coloring
• On the complexity of H-coloring
• Vertex coloring of a graph for memory constrained scenarios
• Title not available (Why is that?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1835680)