TY - JOUR
T1 - The edge-density for K2,t minors
AU - Chudnovsky, Maria
AU - Reed, Bruce
AU - Seymour, Paul
N1 - Funding Information:
E-mail address: [email protected] (P. Seymour). 1 This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. 2 Supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912.
PY - 2011/1
Y1 - 2011/1
N2 - Let H be a graph. If G is an n-vertex simple graph that does not contain H as a minor, what is the maximum number of edges that G can have? This is at most linear in n, but the exact expression is known only for very few graphs H. For instance, when H is a complete graph Kt, the "natural" conjecture, (t-2)n- 1/2(t-1)-(t-2), is true only for t-7 and wildly false for large t, and this has rather dampened research in the area. Here we study the maximum number of edges when H is the complete bipartite graph K2,t. We show that in this case, the analogous "natural" conjecture, 1/2(t+1)(n-1), is (for all t-2) the truth for infinitely many n.
AB - Let H be a graph. If G is an n-vertex simple graph that does not contain H as a minor, what is the maximum number of edges that G can have? This is at most linear in n, but the exact expression is known only for very few graphs H. For instance, when H is a complete graph Kt, the "natural" conjecture, (t-2)n- 1/2(t-1)-(t-2), is true only for t-7 and wildly false for large t, and this has rather dampened research in the area. Here we study the maximum number of edges when H is the complete bipartite graph K2,t. We show that in this case, the analogous "natural" conjecture, 1/2(t+1)(n-1), is (for all t-2) the truth for infinitely many n.
KW - Extremal
KW - Graph
KW - Minors
UR - http://www.scopus.com/inward/record.url?scp=78249273933&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78249273933&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2010.09.001
DO - 10.1016/j.jctb.2010.09.001
M3 - Article
AN - SCOPUS:78249273933
SN - 0095-8956
VL - 101
SP - 18
EP - 46
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 1
ER -