Name
Abstract | ||
|---|---|---|
Let F be a fixed graph of chromatic number r + 1. We prove that for all large n the degree sequence of any F-free graph of order n is, in a sense, close to being dominated by the degree sequence of some r-partite graph. We present two different proofs: one goes via the Regularity Lemma and the other uses a more direct counting argument. Although the latter proof is longer, it gives better estimates and allows F to grow with n. As an application of our theorem, we present new results on the generalization of the Turan problem introduced by Caro and Yuster [Electronic J. Combin. 7 ( 2000)]. |
Year | Venue | Keywords |
|---|---|---|
2005 | ELECTRONIC JOURNAL OF COMBINATORICS | degree sequence |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Chromatic scale,Mathematical proof,Degree (graph theory),Frequency partition of a graph,Critical graph,Mathematics,Lemma (mathematics) | Journal | 12 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 0 |
PageRank | References | Authors |
0.34 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oleg Pikhurko | 1 | 318 | 47.03 |
| Anusch Taraz | 2 | 168 | 37.71 |