Degree sequences of \(F\)-free graphs (Q2583671): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 08:55, 3 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Degree sequences of \(F\)-free graphs |
scientific article |
Statements
Degree sequences of \(F\)-free graphs (English)
0 references
17 January 2006
0 references
The Erdős-Stone theorem states that, for an arbitrary graph \(F\) with chromatic number \(\chi(F)=r+1\), it holds that \[ \text{Max}\bigl\{e (G):\nu(G)=n,\;F\subseteq G\}=t_r(n)+o(n^2)\geq(1-1/r)n(n-1)/2, \] where \(t_r(n)\) is the number of edges of the Turin graph \(T_r(n)\), namely the complete \(r\)-partite graph on \(n\) vertices with parts as equal as possible. In other words, for every \(F\)-free graph \(G\) of order \(n\), there exists an \(r\)-partite graph \(H=T_r(n)\) with almost as many edges as \(G\). In the present paper, the authors consider the question whether analogous statements are true if one compares the degree sequences instead of total number of edges. They prove the following main theorem: Let \(F\) be a fixed non-empty graph of chromatic number \(\chi(F)=r+1\). For any \(\varepsilon >0\) and large \(n\geq n_0(\varepsilon,F)\) the degree sequence \(g_1\geq\cdots\geq g_n\) of any \(F\)-free graph \(G\) is \((\varepsilon n,\varepsilon n)\)-dominated by the degree sequence of some \(r\)-partite graph \(H\) of order \(n\). Two proofs of the main theorem are presented allowing for some technical improvements.
0 references
Turin graph
0 references
Erdős-Stone theorem
0 references
chromatic number
0 references