Disjoint Kr-minors in large graphs with given average degree

Thomas Böhme; Alexandr Kostochka

doi:10.1016/j.ejc.2003.12.017

Disjoint K_r-minors in large graphs with given average degree

Thomas Böhme, Alexandr Kostochka

Mathematics

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

Abstract

It is proved that there are functions f(r) and N(r,s) such that for every positive integer r, s, each graph G with average degree d(G)=2 E(G) / V(G) ≥f(r), and with at least N(r,s) vertices has a minor isomorphic to K_r,s or to the union of s disjoint copies of K_r.

Original language	English (US)
Pages (from-to)	289-292
Number of pages	4
Journal	European Journal of Combinatorics
Volume	26
Issue number	3-4 SPEC. ISS.
DOIs	https://doi.org/10.1016/j.ejc.2003.12.017
State	Published - Apr 2005

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Online availability

10.1016/j.ejc.2003.12.017

Library availability

Discover UIUC Full Text

Cite this

@article{7672a0ef3f8a4c6782466d3a99457b74,

title = "Disjoint Kr-minors in large graphs with given average degree",

abstract = "It is proved that there are functions f(r) and N(r,s) such that for every positive integer r, s, each graph G with average degree d(G)=2 E(G) / V(G) ≥f(r), and with at least N(r,s) vertices has a minor isomorphic to Kr,s or to the union of s disjoint copies of Kr.",

author = "Thomas B{\"o}hme and Alexandr Kostochka",

note = "Funding Information: The second author{\textquoteright}s research is supported in part by the NSF grant DMS-0099608 and by the Dutch–Russian grant NWO-047-008-006.",

year = "2005",

month = apr,

doi = "10.1016/j.ejc.2003.12.017",

language = "English (US)",

volume = "26",

pages = "289--292",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

number = "3-4 SPEC. ISS.",

}

TY - JOUR

T1 - Disjoint Kr-minors in large graphs with given average degree

AU - Böhme, Thomas

AU - Kostochka, Alexandr

N1 - Funding Information: The second author’s research is supported in part by the NSF grant DMS-0099608 and by the Dutch–Russian grant NWO-047-008-006.

PY - 2005/4

Y1 - 2005/4

N2 - It is proved that there are functions f(r) and N(r,s) such that for every positive integer r, s, each graph G with average degree d(G)=2 E(G) / V(G) ≥f(r), and with at least N(r,s) vertices has a minor isomorphic to Kr,s or to the union of s disjoint copies of Kr.

AB - It is proved that there are functions f(r) and N(r,s) such that for every positive integer r, s, each graph G with average degree d(G)=2 E(G) / V(G) ≥f(r), and with at least N(r,s) vertices has a minor isomorphic to Kr,s or to the union of s disjoint copies of Kr.

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

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

U2 - 10.1016/j.ejc.2003.12.017

DO - 10.1016/j.ejc.2003.12.017

M3 - Article

AN - SCOPUS:12944270358

SN - 0195-6698

VL - 26

SP - 289

EP - 292

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 3-4 SPEC. ISS.

ER -