On K s,t-minors in graphs with given average degree, II

A. V. Kostochka; N. Prince

doi:10.1016/j.disc.2012.08.004

On K _s,t-minors in graphs with given average degree, II

A. V. Kostochka, N. Prince

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Let Ks,t* denote the graph obtained from Ks, _t by adding all edges between the s vertices of degree t in it. We show how to adapt the argument of our previous paper [A.V. Kostochka, N. Prince, On Ks, _t-minors in graphs with given average degree, Discrete Math. 308 (2008) 4435-4445] to prove that if tlog ₂t<1000s, then every graph G with average degree at least t+8slog ₂s has a Ks,t* minor. This refines a corresponding result by Kühn and Osthus.

Original language	English (US)
Pages (from-to)	3517-3522
Number of pages	6
Journal	Discrete Mathematics
Volume	312
Issue number	24
DOIs	https://doi.org/10.1016/j.disc.2012.08.004
State	Published - Dec 28 2012

Keywords

Bipartite minors
Dense graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2012.08.004

Library availability

Discover UIUC Full Text

Cite this

@article{53123181c6ba44f39b0060192ffa7b25,

title = "On K s,t-minors in graphs with given average degree, II",

abstract = "Let Ks,t* denote the graph obtained from Ks, t by adding all edges between the s vertices of degree t in it. We show how to adapt the argument of our previous paper [A.V. Kostochka, N. Prince, On Ks, t-minors in graphs with given average degree, Discrete Math. 308 (2008) 4435-4445] to prove that if tlog 2t<1000s, then every graph G with average degree at least t+8slog 2s has a Ks,t* minor. This refines a corresponding result by K{\"u}hn and Osthus.",

keywords = "Bipartite minors, Dense graphs",

author = "Kostochka, {A. V.} and N. Prince",

note = "Funding Information: The research of the first author is supported in part by NSF grant DMS-0965587 , by the Ministry of Education and Science of the Russian Federation (Contract no. 14.740.11.0868) and by grant 09-01-00244 of the Russian Foundation for Basic Research .",

year = "2012",

month = dec,

day = "28",

doi = "10.1016/j.disc.2012.08.004",

language = "English (US)",

volume = "312",

pages = "3517--3522",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "24",

}

TY - JOUR

T1 - On K s,t-minors in graphs with given average degree, II

AU - Kostochka, A. V.

AU - Prince, N.

N1 - Funding Information: The research of the first author is supported in part by NSF grant DMS-0965587 , by the Ministry of Education and Science of the Russian Federation (Contract no. 14.740.11.0868) and by grant 09-01-00244 of the Russian Foundation for Basic Research .

PY - 2012/12/28

Y1 - 2012/12/28

N2 - Let Ks,t* denote the graph obtained from Ks, t by adding all edges between the s vertices of degree t in it. We show how to adapt the argument of our previous paper [A.V. Kostochka, N. Prince, On Ks, t-minors in graphs with given average degree, Discrete Math. 308 (2008) 4435-4445] to prove that if tlog 2t<1000s, then every graph G with average degree at least t+8slog 2s has a Ks,t* minor. This refines a corresponding result by Kühn and Osthus.

AB - Let Ks,t* denote the graph obtained from Ks, t by adding all edges between the s vertices of degree t in it. We show how to adapt the argument of our previous paper [A.V. Kostochka, N. Prince, On Ks, t-minors in graphs with given average degree, Discrete Math. 308 (2008) 4435-4445] to prove that if tlog 2t<1000s, then every graph G with average degree at least t+8slog 2s has a Ks,t* minor. This refines a corresponding result by Kühn and Osthus.

KW - Bipartite minors

KW - Dense graphs

UR - http://www.scopus.com/inward/record.url?scp=84867098991&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867098991&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2012.08.004

DO - 10.1016/j.disc.2012.08.004

M3 - Article

AN - SCOPUS:84867098991

SN - 0012-365X

VL - 312

SP - 3517

EP - 3522

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 24

ER -