| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419656 | Discrete Applied Mathematics | 2009 | 5 Pages |
Abstract
We consider the binding numbers of KrKr-free graphs, and improve the upper bounds on the binding number which force a graph to contain a clique of order rr. For the case r=4r=4, we provide a construction for K4K4-free graphs which have a larger binding number than the previously known constructions. This leads to a counterexample to a conjecture by Caro regarding the neighborhoods of independent sets.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jeremy Lyle, Wayne Goddard,