Multipass greedy coloring of simple uniform hypergraphs

DOI10.1002/rsa.20613zbMath1330.05071arXiv1310.5984MaRDI QIDQ3467582

Jakub Kozik

Publication date: 3 February 2016

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

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

zbMATH Keywords

greedy algorithm; hypergraph coloring; van der Waerden numbers

Mathematics Subject Classification ID

05C65: Hypergraphs

05C15: Coloring of graphs and hypergraphs

Related Items

Colourings of Uniform Hypergraphs with Large Girth and Applications, Extremal problems in hypergraph colourings, Extremal problems for colorings of simple hypergraphs and applications, Improved algorithms for colorings of simple hypergraphs and applications, Colorings of \(b\)-simple hypergraphs, Coloring hypergraphs with bounded cardinalities of edge intersections, Panchromatic 3-colorings of random hypergraphs

Cites Work

• Unnamed Item
• Van der Waerden function and colorings of hypergraphs with large girth
• A remark concerning arithmetic progressions
• Greedy colorings of uniform hypergraphs
• Coloring uniform hypergraphs with few edges
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• Random coloring method in the combinatorial problem of Erdős and Lovász
• An application of Lovász' local lemma-A new lower bound for the van der Waerden number
• A note on random greedy coloring of uniform hypergraphs
• Improved bounds and algorithms for hypergraph 2-coloring
• A Construction for Partitions Which Avoid Long Arithmetic Progressions
• On a property of families of sets
• On a combinatorial problem. II
• A new proof of Szemerédi's theorem