Coloring Sparse Hypergraphs

DOI10.1137/140995805zbMath1338.05078arXiv1404.2895OpenAlexW2963181467MaRDI QIDQ2813339

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

hypergraphschromatic numbertriangle-free graphindependent setssparse hypergraphs

Mathematics Subject Classification ID

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

Related Items (5)

The independent neighborhoods process ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• The triangle-free process
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Covering the vertex set of a graph with subgraphs of smaller degree
• A bound on the chromatic number of a graph
• Coloring graphs with sparse neighborhoods
• A note on the random greedy independent set algorithm
• List coloring triangle-free hypergraphs
• On Brooks' Theorem for Sparse Graphs
• The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)
• Dynamic concentration of the triangle-free process
• Concentration of multivariate polynomials and its applications
• Graph colouring and the probabilistic method

This page was built for publication: Coloring Sparse Hypergraphs