Coloring sparse hypergraphs

DOI10.1137/140995805MaRDI QIDQ2813339zbMATH OpenOpenAlexFDO

Authors Jeff Cooper, Dhruv Mubayi

Publication date 23 June 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberhypergraphstriangle-free graphindependent setssparse hypergraphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Hypergraphs (05C65)

Abstract: Fix $kgeq3$, and let $G$ be a $k$-uniform hypergraph with maximum degree $Delta$. Suppose that for each $l=2,\mathrm{...},k-1$, every set of l vertices of G is in at most $Delt{a}^{(k-l)/(k-1)}/f$ edges. Then the chromatic number of $G$ is $O((Delta/logf{)}^{1/(k-1)})$. This extends results of Frieze and the second author and Bennett and Bohman. A similar result is proved for 3-uniform hypergraphs where every vertex lies in few triangles. This generalizes a result of Alon, Krivelevich, and Sudakov, who proved the result for graphs. Our main new technical contribution is a deviation inequality for positive random variables with expectation less than 1. This may be of independent interest and have further applications.

Recommendations

• On coloring uniform hypergraphs without 3-cycles
• Near-optimal list colorings
• Constructions of sparse uniform hypergraphs with high chromatic number
• Harmonious coloring of uniform hypergraphs
• scientific article; zbMATH DE number 5825874

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• A bound on the chromatic number of a graph
• A note on the random greedy independent set algorithm
• Coloring graphs with sparse neighborhoods
• Concentration of multivariate polynomials and its applications
• Covering the vertex set of a graph with subgraphs of smaller degree
• Dynamic concentration of the triangle-free process
• Graph colouring and the probabilistic method
• List coloring triangle-free hypergraphs
• On Brooks' Theorem for Sparse Graphs
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• The triangle-free process
• The triangle-free process and the Ramsey number \(R(3,k)\)

Cited in

(18)

• Balanced independent sets and colorings of hypergraphs
• Linear coloring of sparse graphs
• Harmonious coloring of uniform hypergraphs
• Coloring unions of nearly disjoint hypergraph cliques
• List colorings of k-partite k-graphs
• Independent sets in hypergraphs
• On coloring uniform hypergraphs without 3-cycles
• The independent neighborhoods process
• Independence number of hypergraphs under degree conditions
• Necessary spectral conditions for coloring hypergraphs
• A GRASP for coloring sparse graphs
• Defective coloring of hypergraphs
• Graph and hypergraph colouring via nibble methods: a survey
• Applications of sparse hypergraph colorings
• Coloring graphs with sparse neighborhoods
• Constructions of sparse uniform hypergraphs with high chromatic number
• Coloring hypergraphs of low connectivity
• On proper colorings of hypergraphs

This page was built for publication: Coloring sparse hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2813339)