Improved algorithms for colorings of simple hypergraphs and applications

DOI10.1016/j.jctb.2015.09.004zbMath1327.05113arXiv1409.6921MaRDI QIDQ896005

Jakub Kozik, Dmitriy A. Shabanov

Publication date: 11 December 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

colorings of hypergraphs; sparse hypergraphs; random recoloring method; van der Waerden number

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C65: Hypergraphs

05C15: Coloring of graphs and hypergraphs

05C07: Vertex degrees

Related Items

Extremal problems in hypergraph colourings, A new lower bound for van der Waerden numbers, Colorings of \(b\)-simple hypergraphs, Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings, New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\), 2-colorings of hypergraphs with large girth, Coloring hypergraphs with bounded cardinalities of edge intersections, Equitable colorings of hypergraphs with few edges, Monochromatic Hilbert cubes and arithmetic progressions, Panchromatic 3-colorings of random hypergraphs, On some generalizations of the property B problem of an \(n\)-uniform hypergraph, Random constructions of hypergraphs with large girth and without panchromatic colorings, Moser-Tardos resampling algorithm, entropy compression method and the subset gas

Cites Work

• Unnamed Item
• A remark concerning arithmetic progressions
• On the chromatic number of set systems
• Coloring uniform hypergraphs with few edges
• Coloring H-free hypergraphs
• Constructions of sparse uniform hypergraphs with high chromatic number
• 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
• Multipass greedy coloring of simple uniform hypergraphs
• Colourings of Uniform Hypergraphs with Large Girth and Applications
• Improved bounds and algorithms for hypergraph 2-coloring
• A Construction for Partitions Which Avoid Long Arithmetic Progressions