Some Colouring Problems and their Complexity

DOI10.1016/S0304-0208(08)73557-6MaRDI QIDQ3968953zbMATH OpenOpenAlexFDO

Authors A. J. Mansfield, D. J. A. Welsh

Publication date 1982

Published in Graph Theory, Proceedings of the Conference on Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-0208(08)73557-6

zbMATH Keywords

chromatic polynomialgraph-theoretic complexity problemsTuring machine

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (05C99) Analysis of algorithms and problem complexity (68Q25)

Cited in

(6)

• On the computational complexity of the order polynomial
• A bibliography on chromatic polynomials
• Hajós and Ore constructions for digraphs
• Grassmann homomorphism and Hajós-type theorems
• Exponential lower bounds for the tree-like Hajós calculus
• Dominic Welsh, 1938--2023

This page was built for publication: Some Colouring Problems and their Complexity

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