scientific article; zbMATH DE number 1789917

MaRDI QIDQ4549228zbMATH OpenFDO

Authors Bruce Reed, Benny Sudakov

Publication date 7 November 2002

Full work available at URL https://arxiv.org/abs/math/0304467

zbMATH Keywords

graph coloringlist-chromatic numberprobabilistic method

Mathematics Subject Classification ID

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

Recommendations

• List colouring when the chromatic number is close to the order of the graph
• A proof of a conjecture of Ohba
• Ohba's conjecture for graphs with independence number five
• Asymptotically the list colouring constants are 1
• List-colourings of graphs

Cited in

(18)

• The chromatic polynomial and list colorings
• List point arboricity of dense graphs
• Towards a version of Ohba's conjecture for improper colorings
• An algebraic criterion for the choosability of graphs
• List coloring of Cartesian products of graphs
• (2+ )-nonrepetitive list colouring of paths
• Ohba's conjecture is true for graphs \(K_{t+2,3,2\ast(k-t-2),1\ast t}\)
• When does the list-coloring function of a graph equal its chromatic polynomial
• On the number of list‐colorings
• Randomly colouring graphs (a combinatorial view)
• Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices
• A proof of a conjecture of Ohba
• List-coloring claw-free graphs with -1 colors
• Ohba's conjecture for graphs with independence number five
• List colouring when the chromatic number is close to the order of the graph
• Minimum non-chromatic-choosable graphs with given chromatic number
• On the choice number of complete multipartite graphs with part size four
• Some colouring problems for Paley graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4549228)