Nice Labeling Problem for Event Structures: A Counterexample

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