Nice Labeling Problem for Event Structures: A Counterexample
Victor D. Chepoi · SIAM Journal on Computing · 2012
In this paper, we present a counterexample to a conjecture of Rozoy and Thiagarajan from 1991 (also called the nice labeling problem) asserting that any (coherent) event structure with finite degree admits a labeling with a finite number of labels or, equivalently, that there exists a function $f:\mathbb{N}\mapsto\mathbb{N}$ such that an event structure with degree $\leq n$ admits a labeling with at most $f(n)$ labels. Our counterexample is based on Burling's construction from 1965 of 3-dimensional box hypergraphs with clique number 2 and arbitrarily large chromatic numbers and the bijection between domains of event structures and median graphs established by Barthélemy and Constantin in 1993.