2013/10/10 by David R. Wood, Wood, David R.
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1310.2972
openalex publication_date 2013/10/10 · arxiv created 2014/08/15 · arxiv updated 2014/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A hypergraph is "d-degenerate" if every subhypergraph has a vertex of degree at most d. A greedy algorithm colours every such hypergraph with at most d+1 colours. We show that this bound is tight, by constructing an r-uniform d-degenerate hypergraph with chromatic number d+1 for all r≥2 and d≥1. Moreover, the hypergraph is triangle-free, where a "triangle" in an r-uniform hypergraph consists of three edges whose union is a set of r+1 vertices.