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

05B40 Packing and covering, See also {11H31, 52C15, 52C17}

05B07 Triple systems

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$.
We verify in the present paper the NP-completeness of the determination of the
(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