How well can a graph be n-colored?

DOI10.1016/0012-365X(81)90023-6zbMath0452.05026OpenAlexW1983592887WikidataQ92200966 ScholiaQ92200966MaRDI QIDQ1148324

Paul M. B. Vitányi

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0012-365x(81)90023-6

zbMATH Keywords

Stirling number of the second kindNP-complete problemequicoloured complete graphErdős-graphn-colourability coefficient of a graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Approximation of Constraint Satisfaction via local search ⋮ New approximation results on graph matching and related problems ⋮ Optimization, approximation, and complexity classes

Cites Work

• Unnamed Item
• Parallel concepts in graph theory
• The Complexity of Near-Optimal Graph Coloring
• Two-Processor Scheduling with Start-Times and Deadlines
• On the Fundamental Problem of Mathematics

This page was built for publication: How well can a graph be n-colored?