Deciding \(k\)-colorability in expected polynomial time

DOI10.1016/S0020-0190(01)00187-9zbMath1046.68079OpenAlexW2007968698MaRDI QIDQ1847370

Michael Krivelevich

Publication date: 24 June 2003

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00187-9

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Approximating the independence number via the \(\vartheta\)-function
• The solution of some random NP-hard problems in polynomial expected time
• A theoretical analysis of backtracking in the graph coloring problem
• Approximate graph coloring by semidefinite programming
• Coloring Clique-free Graphs in Linear Expected Time
• The chromatic number of random graphs
• The chromatic number of random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deciding \(k\)-colorability in expected polynomial time