Affordable Access

Hypergraph Colouring and Degeneracy

Authors
Type
Preprint
Publication Date
Submission Date
Identifiers
arXiv ID: 1310.2972
Source
arXiv
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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments
F