We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Complete graph immersions and minimum degree.
- Authors
Dvořák, Zdeněk; Yepremyan, Liana
- Abstract
Abstract: An <italic>immersion</italic> of a graph <italic>H</italic> in another graph <italic>G</italic> is a one‐to‐one mapping ϕ : V ( H ) → V ( G ) and a collection of edge‐disjoint paths in <italic>G</italic>, one for each edge of <italic>H</italic>, such that the path P u v corresponding to the edge u v has endpoints ϕ ( u ) and ϕ ( v ). The immersion is <italic>strong</italic> if the paths P u v are 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<italic>t</italic> 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.
- Subjects
COMPLETE graphs; IMMERSIONS (Mathematics); TOPOLOGICAL degree; PATHS &; cycles in graph theory; MATHEMATICAL bounds
- Publication
Journal of Graph Theory, 2018, Vol 88, Issue 1, p211
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22206