On the chromatic number of the union of comparability graphs

Abstract

Resolving in a strong sense a problem of Gyárfás on the union of two perfect graphs, we prove that for every pair of positive integers $d$ and $k$, there is a graph $G$ with clique number $k$ and chromatic number $k^d$ that is the union of $d$ comparability graphs. We also show that the chromatic number can be replaced by the fractional chromatic number or $\frac{|V(G)|}{\hat{I}\pm (G)}$.

5 pages; added a strengthening of the main theorem (Theorem 2)