A minimum degree condition forcing complete graph immersion

DOI10.1007/S00493-014-2806-ZzbMATH Open1349.05180arXiv1101.2630OpenAlexW2122404357MaRDI QIDQ397072FDOQ397072

Authors: Matt DeVos, Zdeněk Dvořák, Jacob Fox, Jessica McDonald, Bojan Mohar, Diego Scheide 

Publication date: 14 August 2014

Published in: Combinatorica (Search for Journal in Brave)

Abstract: An immersion of a graph $H$ into a graph $G$ is a one-to-one mapping $f:V(H)oV(G)$ and a collection of edge-disjoint paths in $G$, one for each edge of $H$, such that the path $P_{uv}$ corresponding to edge $uv$ has endpoints $f(u)$ and $f(v)$. The immersion is strong if the paths $P_{uv}$ are internally disjoint from $f(V(H))$. It is proved that for every positive integer $t$, every simple graph of minimum degree at least $200t$ contains a strong immersion of the complete graph $K_t$. For dense graphs one can say even more. If the graph has order $n$ and has $2c{n}^2$ edges, then there is a strong immersion of the complete graph on at least $c^{2}n$ vertices in $G$ in which each path $P_{uv}$ is of length 2. As an application of these results, we resolve a problem raised by Paul Seymour by proving that the line graph of every simple graph with average degree $d$ has a clique minor of order at least $c{d}^{3/2}$, where $c>0$ is an absolute constant. For small values of $t$, $1letle7$, every simple graph of minimum degree at least $t-1$ contains an immersion of $K_t$ (Lescure and Meyniel, DeVos et al.). We provide a general class of examples showing that this does not hold when $t$ is large.

Full work available at URL: https://arxiv.org/abs/1101.2630

Recommendations

• Complete graph immersions and minimum degree
• Complete graph immersions in dense graphs
• Constructing graphs with no immersion of large complete graphs
• An implicit degree condition for cyclability in graphs
• A sufficient condition for immersed-matching of bipartite graphs
• Immersing small complete graphs
• Immersions in highly edge connected graphs
• An implicit degree condition for pancyclicity of graphs
• scientific article; zbMATH DE number 3857140
• Immersion in four-edge-connected graphs

zbMATH Keywords

minimum degreeline graphgraph immersion

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76) Graph minors (05C83)

Cites Work

• Graph minors. XX: Wagner's conjecture
• A bound on the chromatic number of a graph
• The extremal function for complete minors
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Matching theory
• Nonconstructive tools for proving polynomial-time decidability
• Lower bound of the Hadwiger number of graphs by their average degree
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Title not available (Why is that?)
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Topological cliques in graphs II
• Dependent random choice
• Graph coloring and the immersion order
• Immersing small complete graphs
• Title not available (Why is that?)
• Fast Algorithms forK4Immersion Testing
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Title not available (Why is that?)

Cited In (32)

• Immersion and clustered coloring
• Immersion of complete digraphs in Eulerian digraphs
• Complete graph immersions in dense graphs
• Immersing small complete graphs
• On clique immersions in line graphs
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Pseudoachromatic and connected-pseudoachromatic indices of the complete graph
• Immersing complete digraphs
• Large immersions in graphs with independence number 3 and 4
• The treewidth of line graphs
• Immersion of transitive tournaments in digraphs with large minimum outdegree
• A structure theorem for strong immersions
• Strong immersions and maximum degree
• Biclique immersions in graphs with independence number 2
• Logarithmically small minors and topological minors
• Title not available (Why is that?)
• Coloring immersion-free graphs
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• The structure of graphs not admitting a fixed immersion
• A note on clique immersion of strong product graphs
• Constructing graphs with no immersion of large complete graphs
• Hadwiger's conjecture
• Clique immersion in graphs without a fixed bipartite graph
• Clique immersions and independence number
• Lift-contractions
• Lift contractions
• Clique immersion in graph products
• Immersions in highly edge connected graphs
• Complete graph immersions and minimum degree
• Forbidding Kuratowski graphs as immersions
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs
• List-coloring graphs without subdivisions and without immersions

This page was built for publication: A minimum degree condition forcing complete graph immersion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q397072)