Clique immersions and independence number
No hay miniatura disponible
Archivos
Fecha
2022-12
Profesor/a Guía
Facultad/escuela
Idioma
en
Título de la revista
ISSN de la revista
Título del volumen
Editor
Academic Press
Nombre de Curso
Licencia CC
Atribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)
Licencia CC
https://creativecommons.org/licenses/by-nc-nd/4.0/deed.es
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. © 2022
Notas
Indexación: Scopus.
Palabras clave
Hadwiger's Conjecture, Connected Graph, Graph
Citación
European Journal of CombinatoricsOpen AccessVolume 106December 2022 Article number 103550
DOI
10.1016/j.ejc.2022.103550