scientific article; zbMATH DE number 881158

MaRDI QIDQ4878282zbMATH OpenFDO

Authors Noga Alon, Igor Kriz, J. Nešetřil

Publication date 3 December 1996

zbMATH Keywords

parallel algorithmcoloringpolynomial timecolor classshift hypergraph

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Generalized Ramsey theory (05C55) Hypergraphs (05C65)

Recommendations

• A note on near-optimal coloring of shift hypergraphs
• Sure monochromatic subset sums
• Two extensions of Hilbert's cube lemma
• Local rainbow colorings
• A variant of the classical Ramsey problem
• Coloring random graphs
• Improved hardness of approximating chromatic number
• Improved bounds and algorithms for hypergraph 2-coloring
• Graphs with small chromatic numbers are easy to color
• Coloring k-colorable graphs in constant expected parallel time

Cited in

(7)

• Generating infinitely many satisfactory colorings of positive integers
• A note on near-optimal coloring of shift hypergraphs
• Invisible runners in finite fields
• Selection of a large sum-free subset in polynomial time
• Max-norm Ramsey theory
• The chromatic number of random Cayley graphs
• Polychromatic colorings on the integers

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 Q4878282)