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 . 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 . 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.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: November 1, 1999 Final version received: December 1, 2000
Rights and permissions
About this article
Cite this article
Dumitrescu, A., Tóth, G. Ramsey-Type Results for Unions of Comparability Graphs. Graphs Comb 18, 245–251 (2002). https://doi.org/10.1007/s003730200017
Issue Date:
DOI: https://doi.org/10.1007/s003730200017