Large minors in graphs with given independence number

被引：8

作者：

Balogh, Jozsef ^{[1
,2
]}

Kostochk, A. V. ^{[3
,4
]}

机构：

[1] Univ Illinois, Urbana, IL 61801 USA

[2] UC Calif San Diego, Dept Math, La Jolla, CA USA

[3] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[4] Russian Acad Sci, Inst Math, Novosibirsk 630090, Russia

来源：

DISCRETE MATHEMATICS | 2011年 / 311卷 / 20期

基金：

美国国家科学基金会;

关键词：

Clique minor; Independence number; Hadwiger's conjecture; CONJECTURE;

D O I：

10.1016/j.disc.2011.07.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A weakening of Hadwiger's conjecture states that every n-vertex graph with independence number alpha has a clique minor of size at least n/alpha. Extending ideas of Fox (2010)[6], we prove that such a graph has a clique minor with at least n/(2-c)alpha vertices where c > 1/19.2. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：2203 / 2215

页数：13

共 16 条

[1] BALOGH J, DISCUSS MAT IN PRESS
[2] CHUDNOVSKY M, COMBINATORI IN PRESS
[3] DIRAC G. A., 1952, J. London Math. Soc., Vs1-27, P85, DOI 10.1112/jlms/s1-27.1.85
[4] DUCHET P, 1982, GRAPH THEORY, P71
[5] Fajtlowicz S., 1978, Congr. Numer., V21, P269
[6] COMPLETE MINORS AND INDEPENDENCE NUMBER
Fox, Jacob
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (04) : 1313 - 1321
[7] FRADKIN AO, J COMBIN B IN PRESS
[8] Hadwiger H., 1943, Vierteljahr. Naturf. Ges. Zurich, V88, P133
[9] Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture
Kawarabayashi, K
Plummer, MD
Toft, B
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 95 (01) : 152 - 167
[10] Independence number and clique minors
Kawarabayashi, Ken-ichi
Song, Zi-Xia
[J]. JOURNAL OF GRAPH THEORY, 2007, 56 (03) : 219 - 226

← 1 2 →