Coloring Clique-free Graphs in Linear Expected Time

DOI10.1002/rsa.3240030404zbMath0759.05039OpenAlexW2171919542MaRDI 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

zbMATH Keywords

number of graphslinear expected time algorithmcoloring clique-free graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

The average number of linear extensions of a partial order ⋮ Extremal Graph Problems for Graphs with a Color-Critical Vertex ⋮ An expected polynomial time algorithm for coloring 2-colorable 3-graphs ⋮ Deciding \(k\)-colorability in expected polynomial time

Cites Work

• Unnamed Item

This page was built for publication: Coloring Clique-free Graphs in Linear Expected Time