Ramsey-type results for unions of comparability graphs

Authors: Adrian Dumitrescu and Géza Tóth

ABSTRACT

It is well known that the comparability graph of any partially ordered set of $n$ elements contains either a clique or an independent set of size at least $\sqrt{n}$. In this note we show that any graph of $n$ vertices which is the union of two comparability graphs on the same vertex set, contains either a clique or an independent set of size at least $n^{1 \over 3}$. On the other hand, there exist such graphs for which the size of any clique or independent set is at most $n^{0.4118}$. Similar results are obtained for graphs which are unions of a fixed number $k$ comparability graphs. We also show that the same bounds hold for unions of perfect graphs.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-53.ps.gz
DIMACS Home Page