A note on forbidding clique immersions

MaRDI QIDQ396901zbMATHFDO

Authors Matt DeVos, Jessica McDonald, Bojan Mohar, Diego Scheide

Publication date 14 August 2014

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

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

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

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

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

Cited in

(8)

• Immersion of complete digraphs in Eulerian digraphs
• Edge degeneracy: algorithmic and structural results
• Excluding graphs as immersions in surface embedded graphs
• 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
• On objects dual to tree-cut decompositions
• The structure of graphs not admitting a fixed immersion

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)