| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4657363 | Journal of Combinatorial Theory, Series B | 2007 | 8 Pages |
Abstract
An induced subgraph is called homogeneous if it is either a clique or an independent set. Let hom(G) denote the size of the largest homogeneous subgraph of a graph G. In this short paper we study properties of graphs on n vertices with hom(G)⩽Clogn for some constant C. We show that every such graph contains an induced subgraph of order αn in which vertices have different degrees, where α and β depend only on C. This proves a conjecture of Erdős, Faudree and Sós.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
