Contractible edges in 3-connected graphs that preserve a minor

DOI10.1016/J.JCTB.2019.04.003MaRDI QIDQ2284723zbMATH OpenOpenAlexFDO

Authors João Paulo Costalonga

Publication date 15 January 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

3-connectednesscontractible edgesplitter theorem

Mathematics Subject Classification ID

Connectivity (05C40) Graph minors (05C83)

Abstract: Let $G$ be a $3$-connected graph with a $3$-connected (or sufficiently small) simple minor $H$. We establish that $G$ has a forest $F$ with at least $leftlceil(|G|-|H|+1)/2ightceil$ edges such that $G/e$ is $3$-connected with an $H$-minor for each $einE(F)$. Moreover, we may pick $F$ with $|G|-|H|$ edges provided $G$ is triangle-free. These results are sharp. Our result generalizes a previous one by Ando et. al., which establishes that a $3$-connected graph $G$ has at least $leftlceil|G|/2ightceil$ contractible edges. As another consequence, each triangle-free $3$-connected graph has an spanning tree of contractible edges. Our results follow from a more general theorem on graph minors, a splitter theorem, which is also established here.

Recommendations

• Contractible edges and contractible triangles in a 3-connected graph
• An included-minor result for 3-connected graphs with contractible edges
• Contractible edges in 3-connected graphs
• The number of contractible edges in 3-connected graphs
• Contractible edges and removable edges in 3-connected graphs

Cites work

• A splitter theorem on 3-connected matroids
• A survey on contractible edges in graphs of a prescribed vertex connectivity
• Contractible edges in 3-connected graphs
• Contractible edges in triangle-free graphs
• Decomposition of regular matroids
• scientific article; zbMATH DE number 4202289 (Why is no real title available?)
• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• On 3-connected minors of 3-connected matroids and graphs
• On contractible and vertically contractible elements in 3-connected matroids and graphs
• Stabilizers of classes of representable matroids

Cited in

(6)

• An included-minor result for 3-connected graphs with contractible edges
• Properly 3-contractible edges in a minimally 3-connected graph
• A chain theorem for \(3^+\)-connected graphs
• Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge
• Deletable edges in 3-connected graphs and their applications
• A splitter theorem on 3-connected binary matroids and inner fans

This page was built for publication: Contractible edges in 3-connected graphs that preserve a minor

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