Unavoidable parallel minors of 4-connected graphs

DOI10.1002/JGT.20361zbMATH Open1215.05170arXivmath/0606577OpenAlexW2949526788MaRDI QIDQ3633013FDOQ3633013

Authors: Carolyn Chun, Guoli Ding, Bogdan Oporowski, Dirk Vertigan 

Publication date: 16 June 2009

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: A parallel minor is obtained from a graph by any sequence of edge contractions and parallel edge deletions. We prove that, for any positive integer k, every internally 4-connected graph of sufficiently high order contains a parallel minor isomorphic to a variation of K_{4,k} with a complete graph on the vertices of degree k, the k-partition triple fan with a complete graph on the vertices of degree k, the k-spoke double wheel, the k-spoke double wheel with axle, the (2k+1)-rung Mobius zigzag ladder, the (2k)-rung zigzag ladder, or K_k. We also find the unavoidable parallel minors of 1-, 2-, and 3-connected graphs.

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

Recommendations

• Unavoidable parallel minors of regular matroids
• Typical subgraphs of 3- and 4-connected graphs
• Unavoidable minors of large 4-connected bicircular matroids
• Generating internally four-connected graphs
• Internally 4-connected graphs with no \(\{\text{cube}, V_8\}\)-minor

Mathematics Subject Classification ID

Connectivity (05C40) Graph minors (05C83)

Cites Work

• Typical subgraphs of 3- and 4-connected graphs

Cited In (7)

• Unavoidable vertex-minors in large prime graphs
• Unavoidable Induced Subgraphs of Large 2-Connected Graphs
• Unavoidable parallel minors of regular matroids
• Unavoidable topological minors of infinite graphs
• Lift-contractions
• Lift contractions
• Unavoidable minors of graphs of large type

This page was built for publication: Unavoidable parallel minors of 4-connected graphs

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