Coloring Clique-free Graphs in Linear Expected Time
From MaRDI portal
Publication:4019373
DOI10.1002/rsa.3240030404zbMath0759.05039MaRDI QIDQ4019373
Angelika Steger, Hans Jürgen Prömel
Publication date: 16 January 1993
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240030404
05C30: Enumeration in graph theory
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Extremal Graph Problems for Graphs with a Color-Critical Vertex, Deciding \(k\)-colorability in expected polynomial time, The average number of linear extensions of a partial order, An expected polynomial time algorithm for coloring 2-colorable 3-graphs
Cites Work