On the chromatic number of the union of comparability graphs

Wouter Cames van Batenburg; Maria Chudnovsky; Linda Cook; James Davies; Seokbeom Kim; Sang-il Oum

On the chromatic number of the union of comparability graphs

Wouter Cames van Batenburg, Maria Chudnovsky, Linda Cook, James Davies, Seokbeom Kim, Sang-il Oum

arXivarxiv/2606.09415Jun 8, 2026math.COscore 0

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)|}{α(G)}$.

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2606.09415
curl -X POST /api/v1/records/arxiv/2606.09415/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.09415/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'