Constructing colorings for diagrams (Q1329806)

An undirected graph \(G=(V,E)\) is a (Hasse)-diagram if there is a poset \(P=(V,<)\) and an orientation \(\vec E\) of \(E\) such that \((x,y) \in \vec E\) iff \(x<y\) in \(P\) and there is no \(z\) with \(x<z<y\). One then writes \(G=D_ P\). \textit{J. Nešetřil} and \textit{V. Rödl} [Order 3, 321- 330 (1987)] showed that calculating the chromatic number \(\chi\) is NP- hard for diagrams. The authors give bounds for the chromatic number of an arbitrary diagram. Lattices and 2-dimensional posets can have diagrams of arbitrarily large chromatic number as shown by \textit{B. Bollobás} [Algebra Univers. 7, 313-314 (1977; Zbl 0374.06004)] and \textit{I. Křiž} and \textit{J. Nešetřil} [Order 8, No. 1, 41-48 (1991; Zbl 0757.05053)], respectively. The authors construct a family of interval orders \(I_ k\) that are also \(N\)-free for which \(\chi (D_{I_ k}) = k\). Individual bounds are determined for interval orders and for \(N\)-free orders.