Complete immersions in graphs with independence number two and small forbidden subgraphs

Autor(es)

Quiroz, Daniel A. ; Ferreira, CE ; Lee, O ; Miyazawa, FK

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 7-pg., 2021-01-01.

Resumo

The analogue of Hadwiger's conjecture for the immersion order states that every graph G contains the complete graph K-chi(G) as an immersion. Like its minor-order counterpart it is open even for graphs with independence number 2. Let G and H be graphs with independence number at most 2, such that vertical bar V(H)vertical bar <= 4. We show that if G is H-free, then G satisfies the conjecture. (C) 2021 The Authors. Published by Elsevier B.V. (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