| Texto completo | |
| Autor(es): |
Quiroz, Daniel A.
Número total de Autores: 1
|
| Tipo de documento: | Artigo Científico |
| Fonte: | DISCRETE MATHEMATICS; v. 344, n. 6, p. 9-pg., 2021-03-17. |
| Resumo | |
The Lescure-Meyniel conjecture is the analogue of Hadwiger's conjecture for the immersion order. It states that every graph G contains the complete graph K chi(G) as an immersion, and like its minor-order counterpart it is open even for graphs with independence number 2. We show that every graph G with independence number alpha(G) > 2 and no hole of length between 4 and 2 alpha(G) satisfies this conjecture. In particular, every C4-free graph G with alpha(G) = 2 satisfies the Lescure-Meyniel conjecture. We give another generalisation of this corollary, as follows. Let G and H be graphs with independence number at most 2, such that |V(H)| < 4. If G is H-free, then G satisfies the Lescure-Meyniel conjecture. (C) 2021 Elsevier B.V. All rights reserved. (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 |