Back to Search Start Over

A simple proof of the existence of complete bipartite graph immersion in graphs with independence number two

Authors :
Chen, Rong
Deng, Zijian
Publication Year :
2024

Abstract

Hadwiger's conjecture for the immersion relation posits that every graph $G$ contains an immersion of the complete graph $K_{\chi(G)}$. Vergara showed that this is equivalent to saying that every $n$-vertex graph $G$ with $\alpha(G)=2$ contains an immersion of the complete graph on $\lceil\frac{n}{2}\rceil$ vertices. Recently, Botler et al. showed that every $n$-vertex graph $G$ with $\alpha(G)=2$ contains every complete bipartite graph on $\lceil\frac{n}{2}\rceil$ vertices as an immersion. In this paper, we give a much simpler proof of this result.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2412.04522
Document Type :
Working Paper