Improved algorithms for colorings of simple hypergraphs and applications
From MaRDI portal
Publication:896005
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
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