The Ramsey property for graphs with forbidden complete subgraphs |
| |
Authors: | Jaroslav Nešetřil Vojtěch Rödl |
| |
Institution: | Department of Mathematics, Charles University, Prague 8, Czechoslovakia |
| |
Abstract: | The following theorem is proved: Let G be a finite graph with cl(G) = m, where cl(G) is the maximum size of a clique in G. Then for any integer r ≥ 1, there is a finite graph H, also with cl(H) = m, such that if the edges of H are r-colored in any way, then H contains an induced subgraph G′ isomorphic to G with all its edges the same color. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|