Large minors in graphs with given independence number

József Balogh; A. V. Kostochka

doi:10.1016/j.disc.2011.07.003

Large minors in graphs with given independence number

Mathematics

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

Abstract

A weakening of Hadwiger's conjecture states that every n-vertex graph with independence number α has a clique minor of size at least nα. Extending ideas of Fox (2010) [6], we prove that such a graph has a clique minor with at least n(2-c)α vertices where c>119.2.

Original language	English (US)
Pages (from-to)	2203-2215
Number of pages	13
Journal	Discrete Mathematics
Volume	311
Issue number	20
DOIs	https://doi.org/10.1016/j.disc.2011.07.003
State	Published - Oct 28 2011

Keywords

Clique minor
Hadwiger's conjecture
Independence number

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2011.07.003

Library availability

Discover UIUC Full Text

Cite this

@article{4c76a7548b3f45e2b539b35b332e33e5,

title = "Large minors in graphs with given independence number",

abstract = "A weakening of Hadwiger's conjecture states that every n-vertex graph with independence number α has a clique minor of size at least nα. Extending ideas of Fox (2010) [6], we prove that such a graph has a clique minor with at least n(2-c)α vertices where c>119.2.",

keywords = "Clique minor, Hadwiger's conjecture, Independence number",

author = "J{\'o}zsef Balogh and Kostochka, \{A. V.\}",

note = "The second author{\textquoteright}s research was supported in part by NSF grant DMS-0965587 and by the Ministry of education and science of the Russian Federation (Contract no. 14.740.11.0868). The first author{\textquoteright}s research was supported in part by NSF CAREER Grant DMS-0745185 , UIUC Campus Research Board Grants 09072 and 11067 , OTKA Grant K76099 , and TAMOP-4.2.1/B-09/1/KONV-2010-0005 project.",

year = "2011",

month = oct,

day = "28",

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

language = "English (US)",

volume = "311",

pages = "2203--2215",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "20",

}

TY - JOUR

T1 - Large minors in graphs with given independence number

AU - Balogh, József

AU - Kostochka, A. V.

N1 - The second author’s research was supported in part by NSF grant DMS-0965587 and by the Ministry of education and science of the Russian Federation (Contract no. 14.740.11.0868). The first author’s research was supported in part by NSF CAREER Grant DMS-0745185 , UIUC Campus Research Board Grants 09072 and 11067 , OTKA Grant K76099 , and TAMOP-4.2.1/B-09/1/KONV-2010-0005 project.

PY - 2011/10/28

Y1 - 2011/10/28

N2 - A weakening of Hadwiger's conjecture states that every n-vertex graph with independence number α has a clique minor of size at least nα. Extending ideas of Fox (2010) [6], we prove that such a graph has a clique minor with at least n(2-c)α vertices where c>119.2.

AB - A weakening of Hadwiger's conjecture states that every n-vertex graph with independence number α has a clique minor of size at least nα. Extending ideas of Fox (2010) [6], we prove that such a graph has a clique minor with at least n(2-c)α vertices where c>119.2.

KW - Clique minor

KW - Hadwiger's conjecture

KW - Independence number

UR - https://www.scopus.com/pages/publications/84860391216

UR - https://www.scopus.com/pages/publications/84860391216#tab=citedBy

U2 - 10.1016/j.disc.2011.07.003

DO - 10.1016/j.disc.2011.07.003

M3 - Article

AN - SCOPUS:84860391216

SN - 0012-365X

VL - 311

SP - 2203

EP - 2215

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 20

ER -

Large minors in graphs with given independence number

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this