Clique immersions and independence number

Autor(es)

Bustamante, Sebastian ; Quiroz, Daniel A. ; Stein, Maya ; Zamora, Jose

• 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