Hypergraph list coloring and Euclidean Ramsey theory

DOI10.1002/rsa.20361zbMath1232.05146OpenAlexW2026556033MaRDI QIDQ3094608

Noga Alon, Alexandr V. Kostochka

Publication date: 25 October 2011

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20361

zbMATH Keywords

hypergraphsaverage degreelist coloringEuclidean Ramsey theory

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Ramsey theory (05D10)

Related Items

Online containers for hypergraphs, with applications to linear equations ⋮ Extremal problems in hypergraph colourings ⋮ Dense uniform hypergraphs have high list chromatic number ⋮ Chromatic-choosability of hypergraphs with high chromatic number ⋮ Hypergraph containers ⋮ List colorings of multipartite hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The choice number of random bipartite graphs
• Euclidean Ramsey theorems. I
• List coloring hypergraphs
• Hypergraph extension of the Alon-Tarsi list coloring theorem
• New approximation guarantee for chromatic number
• Conditional Hardness for Approximate Coloring
• On list coloring Steiner triple systems
• On the Hardness of 4-Coloring a 3-Colorable Graph
• On the hardness of approximating the chromatic number