Clique immersions in graphs of independence number two with certain forbidden subgraphs

Autor(es)

Quiroz, Daniel A.

• 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