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 numberhypergraphsindependent setssparse hypergraphstriangle-free graph

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• List coloring triangle-free hypergraphs
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• On Brooks' Theorem for Sparse Graphs
• The triangle-free process
• The triangle-free process and the Ramsey number \(R(3,k)\)

Cited in

(20)

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

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)