Ramsey-Type Results for Unions of Comparability Graphs |
| |
| Authors: | Adrian Dumitrescu Géza Tóth |
| |
| Affiliation: | (1) Computer Science, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ 08854-8019, USA. e-mail: dumitres@paul.rutgers.edu, US;(2) Department of Mathematics, Massachusetts of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139-4307, USA and Hungarian Academy of Sciences, Budapest, Hungary. e-mail: toth@math.mit.edu, HU |
| |
| 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. Received: November 1, 1999 Final version received: December 1, 2000 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
