TY - JOUR
T1 - Clique immersions and independence number
AU - Bustamante, Sebastián
AU - Quiroz, Daniel A.
AU - Stein, Maya
AU - Zamora, José
N1 - Publisher Copyright:
© 2022
PY - 2022/12
Y1 - 2022/12
N2 - The analogue of Hadwiger's conjecture for the immersion order states that every graph G contains Kχ(G) as an immersion. If true, this would imply that every graph with n vertices and independence number α contains K⌈[Formula presented]⌉ as an immersion. The best currently known bound for this conjecture is due to Gauthier, Le and Wollan, who recently proved that every graph G contains an immersion of a clique on ⌈[Formula presented]⌉ vertices. Their result implies that every n-vertex graph with independence number α contains an immersion of a clique on ⌈[Formula presented]−1.13⌉ vertices. We improve on this result for all α≥3, by showing that every n-vertex graph with independence number α≥3 contains an immersion of a clique on ⌊[Formula presented]⌋−1 vertices, where f is a nonnegative function.
AB - The analogue of Hadwiger's conjecture for the immersion order states that every graph G contains Kχ(G) as an immersion. If true, this would imply that every graph with n vertices and independence number α contains K⌈[Formula presented]⌉ as an immersion. The best currently known bound for this conjecture is due to Gauthier, Le and Wollan, who recently proved that every graph G contains an immersion of a clique on ⌈[Formula presented]⌉ vertices. Their result implies that every n-vertex graph with independence number α contains an immersion of a clique on ⌈[Formula presented]−1.13⌉ vertices. We improve on this result for all α≥3, by showing that every n-vertex graph with independence number α≥3 contains an immersion of a clique on ⌊[Formula presented]⌋−1 vertices, where f is a nonnegative function.
UR - http://www.scopus.com/inward/record.url?scp=85136695345&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2022.103550
DO - 10.1016/j.ejc.2022.103550
M3 - Article
AN - SCOPUS:85136695345
SN - 0195-6698
VL - 106
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103550
ER -