A minimum degree condition forcing complete graph immersion
From MaRDI portal
Publication:397072
DOI10.1007/s00493-014-2806-zzbMath1349.05180arXiv1101.2630OpenAlexW2122404357MaRDI QIDQ397072
Zdeněk Dvořák, Bojan Mohar, Diego Scheide, Jacob Fox, Jessica McDonald, Matt DeVos
Publication date: 14 August 2014
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1101.2630
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph minors (05C83) Vertex degrees (05C07) Graph operations (line graphs, products, etc.) (05C76)
Related Items
Large immersions in graphs with independence number 3 and 4 ⋮ Immersion of transitive tournaments in digraphs with large minimum outdegree ⋮ Coloring immersion-free graphs ⋮ Clique immersion in graphs without a fixed bipartite graph ⋮ Pseudoachromatic and connected-pseudoachromatic indices of the complete graph ⋮ Forbidding Kuratowski Graphs as Immersions ⋮ Clique immersions and independence number ⋮ Clique immersion in graph products ⋮ Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs ⋮ Forcing clique immersions through chromatic number ⋮ The structure of graphs not admitting a fixed immersion ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Logarithmically small minors and topological minors ⋮ Unnamed Item ⋮ The treewidth of line graphs ⋮ Lift-contractions ⋮ A Structure Theorem for Strong Immersions ⋮ Hadwiger’s Conjecture ⋮ On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion ⋮ Immersion and clustered coloring ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. XX: Wagner's conjecture
- Lower bound of the Hadwiger number of graphs by their average degree
- Graph minors XXIII. Nash-Williams' immersion conjecture
- A bound on the chromatic number of a graph
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- The extremal function for complete minors
- Dependent random choice
- Graph Coloring and the Immersion Order
- Immersing small complete graphs
- On the Problem of Decomposing a Graph into n Connected Factors
- Edge-Disjoint Spanning Trees of Finite Graphs
- Nonconstructive tools for proving polynomial-time decidability
- Fast Algorithms forK4Immersion Testing
- Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
- Topological cliques in graphs II
