On the chromatic number of the union of comparability graphs

2026/06/30 by Wouter Cames van Batenburg, Maria Chudnovsky, Linda Cook +3
Mathematics · #math.CO #msc:05C15

paper · pdf

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

arxiv created 2026/08/03 · arxiv updated 2026/08/04

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 (|V(G)|)/(α(G)).

Citations

• Clique density vs blowups
• A multipartite analogue of Dilworth's Theorem
• Geometric graphs with exponential chromatic number and arbitrary girth
• Induced subgraphs of induced subgraphs of large chromatic number
• On the chromatic number of disjointness graphs of curves
• Coloring, sparseness, and girth