NP-completeness of a family of graph-colouring problems

DOI10.1016/0166-218X(83)90020-3MaRDI QIDQ1835680zbMATHFDO

Authors 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

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

Cited in

(6)

• On the tractability of \(( k , i )\)-coloring
• Exact and parameterized algorithms for \((k,i)\)-coloring
• On the complexity of H-coloring
• Vertex coloring of a graph for memory constrained scenarios
• The complexity of multicolouring
• Sparsification lower bounds for list \(H\)-coloring

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)