Generating internally four-connected graphs
A simple 3-connected graph \(G\) on at least five vertices is called internally 4-connected if for every partition \(\{A,B\}\) of \(E(G)\) wherein \(|A|,|B|\geq 4\), at least four vertices of \(G\) are incident with both an edge in \(A\) and an edge in \(B\). A simple graph \(H'\) is obtained from a simple graph \(H\) by splitting a vertex if \(H\) is obtained from \(H'\) by contracting an edge of \(H'\) both of whose incident vertices are at least 3-valent in \(H'\). The goal of this paper is to prove for internally 4-connected graphs a variant of a result by \textit{P. Seymour} [J. Comb. Theory, Ser. B 28, 305-339 (1980; Zbl 0443.05027)] which prescribes a process yielding a simple 3-connected graph from its largest wheel minor by successively adding edges or splitting vertices. A ``first step toward that goal consists of showing that if \(H\) and \(G\) are internally 4-connected non-isomorphic graphs, ``\(H\) is a minor of \(G\), and they do not belong to a family of exceptional graphs, then there exists a graph \(H'\) isomorphic to a minor of \(G\) and either \(H'\) is obtained from \(H\) by splitting a vertex of \(H'\) or \(H'\) is an internally 4-connected graph obtained from \(H\) by means of one of four possible rather technical constructions. The exceptional graphs for \(H\) are \(K_{3,3}\) and the cube, and for \(G\) are the (planar and Möbius) ladders and the cubic biwheels.
- Typical subgraphs of 3- and 4-connected graphs
- Internally 4-connected graphs with no \(\{\text{cube}, V_8\}\)-minor
- scientific article; zbMATH DE number 512928
- Minimally 3-connected graphs with exactly k non-essential edges
- Odd \(K_{3,3}\) subdivisions in bipartite graphs
- Minimally 3-connected graphs
- Nonseparating K4‐subdivisions in graphs of minimum degree at least 4
- Minimal Cyclic-4-Connected Graphs
- On the decomposition of a 3-connected graph into cyclically 4-edge-connected components
- scientific article; zbMATH DE number 1342090
- Bemerkungen zu Hadwigers Vermutung
- Characterization and Recognition of Partial 3-Trees
- Cyclically five-connected cubic graphs
- Decomposition of regular matroids
- Homomorphiebasen von Graphenmengen
- scientific article; zbMATH DE number 3166039 (Why is no real title available?)
- scientific article; zbMATH DE number 4008436 (Why is no real title available?)
- scientific article; zbMATH DE number 3026377 (Why is no real title available?)
- Matroid 4-connectivity: A deletion-contraction theorem
- Minimal Cyclic-4-Connected Graphs
- On possible counterexamples to Negami's planar cover conjecture
- The spherical genus and virtually planar graphs
- The structure of graphs not topologically containing the Wagner graph
- The structure of quasi 4-connected graphs
- Zur Klassifikation der endlichen Graphen nach H. Hadwiger und K. Wagner
- Über einen Satz von K.Wagner zum Vierfarbenproblem
- Linear connectivity forces large complete bipartite minors
- Towards a splitter theorem for internally 4-connected binary matroids. VI
- Matroid 4-connectivity: A deletion-contraction theorem
- A constructive characterization of 4-connected graphs
- Internally 4-connected graphs with no \(\{\text{cube}, V_8\}\)-minor
- Graphs with no 7-wheel subdivision
- Generating weakly 4-connected matroids
- A characterization of graphs with no octahedron minor
- Towards a splitter theorem for internally 4-connected binary matroids. IX. The theorem.
- Non-planar extensions of subdivisions of planar graphs
- Unavoidable parallel minors of 4-connected graphs
- Towards a splitter theorem for internally 4-connected binary matroids. III
- Towards a splitter theorem for internally 4-connected binary matroids. IV
- Towards a splitter theorem for internally 4-connected binary matroids. V
- Towards a splitter theorem for internally 4-connected binary matroids. VIII: Small matroids.
- Towards a splitter theorem for internally 4-connected binary matroids. VII
- A chain theorem for internally 4-connected binary matroids
- Typical subgraphs of 3- and 4-connected graphs
- Some recent progress and applications in graph minor theory
This page was built for publication: Generating internally four-connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850601)
