Sparse graphs usually have exponentially many optimal colorings

zbMath0989.05106MaRDI QIDQ1601114

Michael Krivelevich

Publication date: 1 July 2002

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/121889

zbMATH Keywords

chromatic numberrandom graphoptimal colorings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Related Items (1)

A combinatorial algorithm for the TDMA message scheduling problem

This page was built for publication: Sparse graphs usually have exponentially many optimal colorings