Isma Bouchemakh
On the chromatic number of order-interval hypergraphs
The paper is published: Rostocker Mathematisches Kolloquium, Rostock. Math. Kolloq. 54, 81-89 (2000)
MSC:
05C65 Hypergraphs
05C15 Chromatic theory of graphs and maps
Abstract: Let $P$ a finite poset. We consider the hypergraph $\mathfrak H(P)$ whose
vertices are the points of $P$ and whose edges are the maximal intervals in $P$.
(strong) chromatic number $\gamma(\mathfrak H(P))$. We give some exact or asymptotic
values of $\gamma(\mathfrak H(P))$ if $P$ is the subposet of the Boolean lattice
induced by consecutive levels $P_{l} \cup \cdots \cup P_{u}$. Moreover, we
determine $\gamma(\mathfrak H(P))$ for interval orders $P$.
Keywords: Partial order, Boolean lattice, interval, chromatic number, packing system, Steiner system, large set, $NP$-completeness