TY - JOUR

T1 - Large Immersions in Graphs with Independence Number 3 and 4

AU - Bustamante, S.

AU - Quiroz, D. A.

AU - Stein, M.

AU - Zamora, J.

N1 - Funding Information:
1 Supported by CONICYT, PIA/Apoyo a Centros Científicos y Tecnológicos de Excelencia con Finan-ciamiento Basal AFB170001. 2 Supported by CONICYT Doctoral Fellowship grant 21141116. 3 Supported by FONDECYT Regular grant 1183080. 4 Supported by FONDECYT Regular grant 1180994. 5 Email: {dquiroz, mstein, sbustamante}@dim.uchile.cl 6 Email: [email protected]

PY - 2019/1/1

Y1 - 2019/1/1

N2 - The analogue of Hadwiger's conjecture for the immersion order, a conjecture independently posed by Lescure and Meyniel, and by Abu-Khzam and Langston, states that every graph G which does not contain the complete graph Kt+1 as an immersion satisfies χ(G) ≤ t. If true, this conjecture would imply that every graph with n vertices and independence number α contains K⌈n/3.5α-c⌉ as an immersion (and if α = 2, the two statements are known to be equivalent). The immersion conjecture has been tackled with more success than its graph minors counterpart: not only is a linear upper bound known for the chromatic number of Kt+1-immersion-free graphs, but the best bound currently known is very close to optimal. Namely, the currently best bound in this respect is due to Gauthier, Le and Wollan, who recently proved that every graph not containing Kt+1 as an immersion satisfies χ(G) ≤ 3.54t + 7. Their result implies that any graph with n vertices and independence number α contains K2⌈n/5⌉ as an immersion, where c < 1.98. Moreover, the same authors prove that every graph of independence number 2 contains K⌊n/α⌋ as an immersion. We show that any graph with n vertices and independence number 3 contains a clique immersion on at least ⌈2n/9⌉ vertices, and any graph with n vertices and independence number 4 contains a clique immersion on at least ⌈4n/27⌉ -1 vertices. Thus, comparing to the bound from above, in both cases we roughly double the size of the immersion obtained.

AB - The analogue of Hadwiger's conjecture for the immersion order, a conjecture independently posed by Lescure and Meyniel, and by Abu-Khzam and Langston, states that every graph G which does not contain the complete graph Kt+1 as an immersion satisfies χ(G) ≤ t. If true, this conjecture would imply that every graph with n vertices and independence number α contains K⌈n/3.5α-c⌉ as an immersion (and if α = 2, the two statements are known to be equivalent). The immersion conjecture has been tackled with more success than its graph minors counterpart: not only is a linear upper bound known for the chromatic number of Kt+1-immersion-free graphs, but the best bound currently known is very close to optimal. Namely, the currently best bound in this respect is due to Gauthier, Le and Wollan, who recently proved that every graph not containing Kt+1 as an immersion satisfies χ(G) ≤ 3.54t + 7. Their result implies that any graph with n vertices and independence number α contains K2⌈n/5⌉ as an immersion, where c < 1.98. Moreover, the same authors prove that every graph of independence number 2 contains K⌊n/α⌋ as an immersion. We show that any graph with n vertices and independence number 3 contains a clique immersion on at least ⌈2n/9⌉ vertices, and any graph with n vertices and independence number 4 contains a clique immersion on at least ⌈4n/27⌉ -1 vertices. Thus, comparing to the bound from above, in both cases we roughly double the size of the immersion obtained.

KW - chromatic number

KW - Graph immersion

KW - Hadwiger's conjecture

KW - independence number

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

U2 - 10.1016/j.entcs.2019.08.020

DO - 10.1016/j.entcs.2019.08.020

M3 - Conference article

AN - SCOPUS:85076257594

VL - 346

SP - 221

EP - 228

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

SN - 1571-0661

T2 - 10th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019

Y2 - 2 June 2019 through 7 June 2019

ER -