DIMACS TR: 99-53
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