A minimum degree condition forcing complete graph immersion

DOI10.1007/S00493-014-2806-ZMaRDI QIDQ397072zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(32)

• Immersion and clustered coloring
• Complete graph immersions in dense graphs
• Immersion of complete digraphs in Eulerian digraphs
• Immersing small complete graphs
• On clique immersions in line graphs
• Immersing complete digraphs
• Pseudoachromatic and connected-pseudoachromatic indices of the complete graph
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• 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
• Coloring immersion-free graphs
• Logarithmically small minors and topological minors
• scientific article; zbMATH DE number 4144020 (Why is no real title available?)
• The structure of graphs not admitting a fixed immersion
• On the Number of Cliques in Graphs with a Forbidden Subdivision or 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)