Clique immersions and independence number

Sebastián Bustamante, Daniel A. Quiroz, Maya Stein, José Zamora

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

Resumen

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.

Idioma originalInglés
Número de artículo103550
PublicaciónEuropean Journal of Combinatorics
Volumen106
DOI
EstadoPublicada - dic. 2022

Áreas temáticas de ASJC Scopus

  • Matemáticas discretas y combinatorias

Huella

Profundice en los temas de investigación de 'Clique immersions and independence number'. En conjunto forman una huella única.

Citar esto