2025/06/11 by Fábio Botler, Cristina G. Fernandes, Botler, Fábio +11
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2506.09768
openalex publication_date 2025/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An immersion of a graph H in a graph G is a minimal subgraph I of G for which there is an injection \rm i \colon V(H) → V(I) and a set of edge-disjoint paths \Pe: e ∈ E(H)\ in I such that the end vertices of Puv are precisely \rm i(u) and \rm i(v). The immersion analogue of Hadwiger Conjecture (1943), posed by Lescure and Meyniel (1985), asks whether every graph G contains an immersion of Kχ(G). Its restriction to graphs with independence number 2 has received some attention recently, and Vergara (2017) raised the weaker conjecture that every graph with independence number 2 has an immersion of Kχ(G). This implies that every graph with independence number 2 has an immersion of K\lceil n/2 \rceil. In this paper, we verify Vergara Conjecture for graphs with bounded maximum degree. Specifically, we prove that if G is a graph with independence number 2, maximum degree less than 2n/3 - 1 and clique covering number at most 3, then G contains an immersion of Kχ(G) (and thus of K\lceil n/2 \rceil). Using a result of Jin (1995), this implies that if G is a graph with independence number 2 and maximum degree less than 19n/29 - 1, then G contains an immersion of Kχ(G) (and thus of K\lceil n/2 \rceil).