Nice labeling problem for event structures: a counterexample

DOI10.1137/110837760MaRDI QIDQ3143290zbMATH OpenOpenAlexWikidataFDO

Authors Victor Chepoi

Publication date 29 November 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.1207

zbMATH Keywords

box hypergraphCAT(0) cubical complexdomainevent structuremedian graphnice labeling

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Combinatorics in computer science (68R05)

Abstract: 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:mathbbNmapstomathbbN$ such that an event structure with degree $len$ 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.

Recommendations

• A Nice Labelling for Tree-Like Event Structures of Degree 3
• A Nice labelling for tree-like event structures of degree 3
• scientific article; zbMATH DE number 67680
• Finite labelling problem in event structures
• A counterexample to Thiagarajan's conjecture on regular event structures

Cited in

(16)

• A compact representation for minimizers of k-submodular functions
• The simplicial boundary of a CAT(0) cube complex
• Medians in median graphs and their cube complexes in linear time
• A counterexample to Thiagarajan's conjecture on regular event structures
• Distance and routing labeling schemes for cube-free median graphs
• Topological properties of event structures
• Directed homotopy in non-positively curved spaces
• Weakly Modular Graphs and Nonpositive Curvature
• A Nice Labelling for Tree-Like Event Structures of Degree 3
• On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes
• scientific article; zbMATH DE number 4770 (Why is no real title available?)
• A counterexample to Thiagarajan's conjecture on regular event structures
• First-order logic axiomatization of metric graph theory
• Medians in median graphs and their cube complexes in linear time
• Median geometry and applications. Abstracts from the workshop held February 15--20, 2026
• A Nice labelling for tree-like event structures of degree 3

This page was built for publication: Nice labeling problem for event structures: a counterexample

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3143290)