Affordable Access

Hypergraph Colouring and Degeneracy

Authors
  • Wood, David R.
Type
Preprint
Publication Date
Aug 14, 2014
Submission Date
Oct 10, 2013
Identifiers
arXiv ID: 1310.2972
Source
arXiv
License
Yellow
External links

Abstract

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\geq2$ and $d\geq1$. 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.

Report this publication

Statistics

Seen <100 times