Graphs with small chromatic numbers are easy to color

DOI10.1016/0020-0190(89)90200-7zbMath0665.68055OpenAlexW2000890568MaRDI QIDQ1116349

Luděk Kučera

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90200-7

zbMATH Keywords

graph coloringpolynomial time algorithmchromatic numberprobabilistic analysis of algorithms

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)

Related Items (4)

On independent sets in random graphs ⋮ Expected complexity of graph partitioning problems ⋮ Random I‐colorable graphs ⋮ Coloring k-colorable graphs in constant expected parallel time

Cites Work

• Almost all k-colorable graphs are easy to color
• Unnamed Item
• Unnamed Item

This page was built for publication: Graphs with small chromatic numbers are easy to color