List colouring when the chromatic number is close to the order of the graph

DOI10.1007/s00493-005-0010-xzbMath1063.05049OpenAlexW2115859130MaRDI QIDQ558319

Benjamin Sudakov, Bruce A. Reed

Publication date: 5 July 2005

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-005-0010-x

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

Ohba's conjecture is true for graphs \(K_{t+2,3,2\ast(k-t-2),1\ast t}\), Graphs with $\chi=\Delta$ Have Big Cliques, Application of polynomial method to on-line list colouring of graphs, Towards an on-line version of Ohba's conjecture, Randomly colouring graphs (a combinatorial view), Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices, Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker, Chromatic-choosability of hypergraphs with high chromatic number, On choosability of some complete multipartite graphs and Ohba's conjecture, A weaker version of a conjecture on list vertex arboricity of graphs, Ohba's conjecture for graphs with independence number five, Towards a version of Ohba's conjecture for improper colorings, On the choice number of complete multipartite graphs with part size four, Ohba's conjecture is true for graphs with independence number at most three, Coloring Graphs with Dense Neighborhoods, List point arboricity of dense graphs, A Proof of a Conjecture of Ohba, An algebraic criterion for the choosability of graphs