Immersions of large cliques in graphs with independence number 2 and bounded maximum degree
Immersions of large cliques in graphs with independence number 2 and bounded maximum degree
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) \to V(I)$ and a set of edge-disjoint paths $\{P_e: e \in E(H)\}$ in $I$ such that the end vertices of $P_{uv}$ 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_{\chi(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_{\chi(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_{\chi(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_{\chi(G)}$ (and thus of $K_{\lceil n/2 \rceil}$).
Fábio Botler、Cristina G. Fernandes、Carla N. Lintzmayer、Rui A. Lopes、Suchismita Mishra、Bruno L. Netto、Maycon Sambinelli
数学
Fábio Botler,Cristina G. Fernandes,Carla N. Lintzmayer,Rui A. Lopes,Suchismita Mishra,Bruno L. Netto,Maycon Sambinelli.Immersions of large cliques in graphs with independence number 2 and bounded maximum degree[EB/OL].(2025-06-11)[2025-06-30].https://arxiv.org/abs/2506.09768.点此复制
评论