Nice labeling problem for event structures: a counterexample

Details Nice labeling problem for event structures: a counterexample Nice labeling problem for event structures: a counterexample

2011-07-06

arxiv.org/abs/1107.1207v1

Mathematics

Combinatorics

Scientific paper

In this note, we present a counterexample to a conjecture of Rozoy and Thiagarajan from 1991 (called also 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 $\le n$ admits a labeling with at most $f(n)$ labels. Our counterexample is based on the 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\'elemy and Constantin in 1993.

Affiliated with

Also associated with

No associations

Rating

Nice labeling problem for event structures: a counterexample does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nice labeling problem for event structures: a counterexample, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nice labeling problem for event structures: a counterexample will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-678847