Clique immersions and independence number

Author(s)

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

• Document type: Journal article
• Source: EUROPEAN JOURNAL OF COMBINATORICS; v. 106, p. 9-pg., 2022-08-19.

Abstract

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)

• FAPESP's process: 19/13364-7 - Extremal and structural problems in graph theory
• Grantee: Cristina Gomes Fernandes
• Support Opportunities: Regular Research Grants