Dense graphs have K-3,K-t minors

作者：Kostochka A V^*; Prince N

来源：Discrete Mathematics, 2010, 310(20): 2637-2654.

DOI：10.1016/j.disc.2010.03.026

• Bipartite minors
• Dense graphs

Let K-3,K-t* denote the graph obtained from K-3,K-t by adding all edges between the three vertices of degree t in it. We prove that for each t >= 6300 and n >= t + 3, each n-vertex graph G with e(G) > 1/2(t + 3)(n - 2) + 1 has a K-3,K-t*-minor. The bound is sharp in the sense that for every t, there are infinitely many graphs G with e(G) = 1/2(t + 3)(vertical bar V(G)vertical bar - 2) + 1 that have no K-3,K-t-minor. The result confirms a partial case of the conjecture by Woodall and Seymour that every (s + t)-chromatic graph has a K-s,K-t-minor.

• 出版日期2010-10-28