Geodesic
Degree sequences of \(F\)-free graphs
The electronic journal of combinatorics, Tome 12 (2005)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 Turán problem introduced by Caro and Yuster [Electronic J. Combin. 7 (2000)].
DOI : 10.37236/1966
Classification : 05C35, 05C07, 05C15
Mots-clés : Turin graph, Erdős-Stone theorem, chromatic number 
@article{10_37236_1966,
     author = {Oleg Pikhurko and Anusch Taraz},
     title = {Degree sequences of {\(F\)-free} graphs},
     journal = {The electronic journal of combinatorics},
     year = {2005},
     volume = {12},
     doi = {10.37236/1966},
     zbl = {1082.05052},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1966/}
}
TY  - JOUR
AU  - Oleg Pikhurko
AU  - Anusch Taraz
TI  - Degree sequences of \(F\)-free graphs
JO  - The electronic journal of combinatorics
PY  - 2005
VL  - 12
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1966/
DO  - 10.37236/1966
ID  - 10_37236_1966
ER  - 
%0 Journal Article
%A Oleg Pikhurko
%A Anusch Taraz
%T Degree sequences of \(F\)-free graphs
%J The electronic journal of combinatorics
%D 2005
%V 12
%U http://geodesic.mathdoc.fr/articles/10.37236/1966/
%R 10.37236/1966
%F 10_37236_1966
Oleg Pikhurko; Anusch Taraz. Degree sequences of \(F\)-free graphs. The electronic journal of combinatorics, Tome 12 (2005). doi: 10.37236/1966

Cité par Sources :