Large Cliques in -Free Graphs |
| |
Authors: | András Gyárfás Alice Hubenko József Solymosi |
| |
Institution: | (1) Computer and Automation Research Institute, Hungarian Academy of Sciences; E-mail: Gyarfas@luna.aszi.sztaki.hu, HU;(2) Computer and Automation Research Institute, Hungarian Academy of Sciences; E-mail: hubenko@msci.memphis.edu, HU;(3) Computer and Automation Research Institute, Hungarian Academy of Sciences; E-mail: solymosi@euclid.ucsd.edu, HU |
| |
Abstract: | Dedicated to the memory of Paul Erdős
A graph is called -free if it contains no cycle of length four as an induced subgraph. We prove that if a -free graph has n vertices and at least edges then it has a complete subgraph of vertices, where depends only on . We also give estimates on and show that a similar result does not hold for H-free graphs––unless H is an induced subgraph of . The best value of is determined for chordal graphs.
Received October 25, 1999
RID="*"
ID="*" Supported by OTKA grant T029074.
RID="**"
ID="**" Supported by TKI grant stochastics@TUB and by OTKA grant T026203. |
| |
Keywords: | AMS Subject Classification (2000) Classes: 05C35 |
本文献已被 SpringerLink 等数据库收录! |