Comparability-Graph Unions Can Have Chromatic Number k^d

Comparability graphs are perfect, so each one individually has chromatic number equal to its clique number. This paper shows that the relationship can fail dramatically after taking an edge union. For every pair of positive integers $d$ and $k$, the authors construct a graph $G$ that is the union of $d$ comparability graphs, has clique number $k$, and has chromatic number $k^d$. The result resolves, in the strong sense stated by the authors, a problem of Gyárfás concerning unions of perfect graphs.

The distinction is structural: a coloring of the union must respect the edges from every comparability-graph layer at once. Thus, although each layer separately satisfies $\chi=\omega$, their union can require many more colors than its clique number suggests.

Core Contribution

For every $d,k\geq1$, the main theorem gives a graph satisfying

where $G$ is the union of $d$ comparability graphs. The exponent is the number of layers, so the gap between clique number and chromatic number grows as more comparability-graph structures are combined.

Technical Approach

When all $a_i\leq m/2$, the proof bounds the probability that such a set is independent using pairwise products of the part sizes, followed by a union bound. It treats the complementary case, in which one part contains more than $m/2$ vertices of $A$, separately. The displayed calculation introduces a parameter $\Lambda$ and chooses it so that $\theta=e^2h2^{2-\Lambda}<1$, making the resulting series converge.

For sufficiently large $m$, this argument shows that the random graph has no independent set larger than $m$ with probability tending to one. Since each vertex class is independent, the construction has $\alpha(G)=m$. The proof also establishes positive probability that the graph simultaneously has girth greater than $g$ and independence number $m$.

Results and Analysis

This is a general mathematical result rather than an empirical evaluation: it applies to every positive pair $(d,k)$. The fractional-chromatic and independence-ratio versions strengthen the conclusion beyond ordinary chromatic number alone.

For graph theorists studying colorings of graph unions and subclasses of perfect graphs, the theorem demonstrates that perfection-style chromatic bounds do not transfer directly through edge unions. The result is an existence theorem supported by a combinatorial and probabilistic proof.