List coloring of random and pseudo-random graphs

DOI10.1007/s004939970001zbMath0985.05046OpenAlexW2038200513MaRDI QIDQ1977428

Michael Krivelevich, Noga Alon, Benjamin Sudakov

Publication date: 14 May 2000

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004939970001

zbMATH Keywords

random graphschromatic number

Mathematics Subject Classification ID

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

Related Items

Concentration of non‐Lipschitz functions and applications ⋮ Random Latin square graphs ⋮ New bounds for Ryser’s conjecture and related problems ⋮ Discrepancy properties for random regular digraphs ⋮ On the Chromatic Number of Random Cayley Graphs ⋮ On-line list colouring of random graphs ⋮ Random regular graphs of high degree ⋮ Equitable coloring of random graphs ⋮ The chromatic number of random Cayley graphs ⋮ On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs ⋮ Coloring graphs with sparse neighborhoods ⋮ More spectral bounds on the clique and independence numbers ⋮ The choice number of random bipartite graphs ⋮ Choosability in random hypergraphs ⋮ Some colouring problems for Paley graphs