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.)

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)