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.
scientific article; zbMATH DE number 1843822
scientific article