Name
Abstract | ||
|---|---|---|
Let H(3,1) denote the complete bipartite graph K3,3 with an edge deleted. For given graphs G and F, the Turán numbers (G, F) denote the maximum number of edges in a subgraph of G containing no copy of F. We prove that ${\rm ex} (K_{n,n}, H(3,1)) \le ({4 / \sqrt 7}n ^{3/2} +O(n) \approx 1.5119 n ^{3/2} +O(n)$) and that ${\rm ex} (K_{n}, H(3,1)) \le (1/5) \sqrt {15 }\ n^{3/2} +O(n) \approx 0.7746 n ^{3/2} \,+ O(n)$, which improve earlier results of Mubayi-West [13] and Füredi-West [10], respectively. The generalized Ramsey parameter r(G, F, q) denotes the minimum number of colors needed to edge-color G such that every copy of F in G receives at least q colors. As an immediate consequence, the above results imply that $r(K_{n,n}, K_{3,3}, 3) (\sqrt 7 /4 -o(1) ) \sqrt n \approx (0.6614 -o(1) ) \sqrt n$ and that $r(K_{n}, K_{3,3}, 3) ( \sqrt {15}/6 -o(1) ) \sqrt n \approx ( 0.6455 -o(1) ) \sqrt n$, respectively. These improve the corresponding bounds given by Mubayi [12] recently. © 2005 Wiley Periodicals |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1002/jgt.v51:3 | Journal of Graph Theory |
DocType | Volume | Issue |
Journal | 51 | 3 |
Citations | PageRank | References |
1 | 1.01 | 6 |
Authors | ||
1 | ||