Premium
Complete graph immersions and minimum degree
Author(s) -
Dvořák Zdeněk,
Yepremyan Liana
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22206
Subject(s) - combinatorics , mathematics , disjoint sets , conjecture , immersion (mathematics) , graph , cubic graph , discrete mathematics , line graph , voltage graph , geometry
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.