The complexity of multicolouring

DOI10.1016/0012-365X(88)90050-7zbMath0662.05026OpenAlexW1988055543MaRDI QIDQ1113919

Graham E. Farr

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0012-365x(88)90050-7

zbMATH Keywords

computational complexityvertex colouring

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

• Kneser's conjecture, chromatic number, and homotopy
• n-tuple colorings and associated graphs
• Multicolorings, measures and games on graphs
• Some simplified NP-complete graph problems
• NP-completeness of a family of graph-colouring problems
• 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: The complexity of multicolouring