Complete graph immersions and minimum degree

An immersion of a graph H in another graph G is a one‐to‐one mapping ϕ : V ( H ) → V ( G ) and a collection of edge‐disjoint paths in G , one for each edge of H , such that the path P u vcorresponding to the edge u v has endpoints ϕ ( u ) and ϕ ( v ) . The immersion is strong if the paths P u vare internally disjoint from ϕ ( V ( H ) ) . We prove that every simple graph of minimum degree at least 11 t + 7 contains a strong immersion of the complete graph K t . This improves on previously known bound of minimum degree at least 200 t obtained by DeVos et al. Our result supports a conjecture of Lescure and Meyniel (also independently proposed by Abu‐Khzam and Langston), which is the analogue of famous Hadwiger’s conjecture for immersions and says that every graph without a K t ‐immersion is ( t − 1 ) ‐colorable.