A note on forbidding clique immersions

zbMATH Open1295.05194arXiv1207.2117MaRDI QIDQ396901FDOQ396901

Jessica McDonald, Matt DeVos, Bojan Mohar, Diego Scheide

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Robertson and Seymour proved that the relation of graph immersion is well-quasi-ordered for finite graphs. Their proof uses the results of graph minors theory. Surprisingly, there is a very short proof of the corresponding rough structure theorem for graphs without $K_t$-immersions; it is based on the Gomory-Hu theorem. The same proof also works to establish a rough structure theorem for Eulerian digraphs without $vec{K}_t$-immersions, where $vec{K}_t$ denotes the bidirected complete digraph of order $t$.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The structure of graphs not admitting a fixed immersion
• Clique immersion in graphs without a fixed bipartite graph
• Excluding graphs as immersions in surface embedded graphs
• The structure of graphs with no W4 immersion
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Cited In (7)

• Immersion of complete digraphs in Eulerian digraphs
• The structure of graphs with no W4 immersion
• A structure theorem for strong immersions
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• The structure of graphs not admitting a fixed immersion
• On objects dual to tree-cut decompositions
• Edge degeneracy: algorithmic and structural results

This page was built for publication: A note on forbidding clique immersions

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