The complexity of multicolouring

DOI10.1016/0012-365X(88)90050-7MaRDI QIDQ1113919zbMATH OpenOpenAlexFDO

Authors Graham 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

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

Review text

A graph G is said to be (r,s)-colourable if each vertex of G can be assigned r colours from a given set of s colours so that adjacent vertices receive disjoint colour sets. \textit{R. W. Irving} [Discrete Appl. Math. 5, 111-117 (1983; Zbl 0504.05032)] proved that for any positive integer r, \((r,2r+1)-\)colourability is NP-complete. The present author extends Irving's result by showing that for all positive integers r and s with \(s>2r\), (r,s)-colourability is also NP-complete. The proof uses the fact that the usual \(\left( \begin{matrix} s\\ r\end{matrix} \right)\)-colouring of a graph is NP-complete.

Recommendations

• Some results concerning the complexity of restricted colorings of graphs
• On the complexity of H-coloring
• The complexity of some graph colouring problems
• scientific article; zbMATH DE number 4008418
• The complexity of changing colourings with bounded maximum degree

Cites work

• A (<5)-Colour Theorem for Planar Graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Kneser's conjecture, chromatic number, and homotopy
• Multicolorings, measures and games on graphs
• n-tuple colorings and associated graphs
• NP-completeness of a family of graph-colouring problems
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Some simplified NP-complete graph problems
• The Complexity of Near-Optimal Graph Coloring

Cited in

(8)

• The algorithmic complexity of colour switching
• Adaptive multicolouring
• Colorings and doubled colorings of virtual doodles
• Colors Make Theories Hard
• scientific article; zbMATH DE number 5071318 (Why is no real title available?)
• Mixing Color Coding-Related Techniques
• Multicolour Discrepancies
• Colouring Isonemal Fabrics with more than two Colours by Thick Striping

This page was built for publication: The complexity of multicolouring

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