| Texto completo | |
| Autor(es): |
Bustamante, Sebastian
;
Quiroz, Daniel A.
;
Stein, Maya
;
Zamora, Jose
Número total de Autores: 4
|
| Tipo de documento: | Artigo Científico |
| Fonte: | EUROPEAN JOURNAL OF COMBINATORICS; v. 106, p. 9-pg., 2022-08-19. |
| Resumo | |
The analogue of Hadwiger's conjecture for the immersion order states that every graph G contains K-chi(G) as an immersion. If true, this would imply that every graph with n vertices and independence number alpha contains K inverted right perpendiculexpressionr n/alpha right ceiling as an immersion. The best currently known bound for this conjecture is due graph G contains an immersion of a clique on inverted right perpendiculexpressionr chi(G)-4/3.54 right ceiling to vertices. Their result implies that every n-vertex graph with independence number alpha contains an immersion of a clique on inverted right perpendiculexpressionr n/3.54 alpha - 1.13 right ceiling vertices. We improve on this result for all alpha > 3, by showing that every n-vertex graph with independence number alpha > 3 contains an immersion of a clique on left floor n/2.25 alpha-f(alpha) right floor - 1 vertices, where f is a nonnegative function. (C) 2022 Published by Elsevier Ltd. (AU) | |
| Processo FAPESP: | 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos |
| Beneficiário: | Cristina Gomes Fernandes |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |