Generating internally four-connected graphs
type: Item
instance of: scholarly article
title: Generating internally four-connected graphs
zbMATH Open document ID: 1028.05053
author: Thor Johnson
author: Robin Thomas
published in: Journal of Combinatorial Theory. Series B
publication date: 2002-12-10T00:00:00Z
review text: 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.
reviewed by: Mark E. Watkins
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1843822
zbMATH Keywords: internally 4-connected
zbMATH Keywords: subdivision
zbMATH Keywords: minor
zbMATH Keywords: splitting a vertex
zbMATH Keywords: ladder
zbMATH Keywords: Möbius ladder
zbMATH Keywords: homeomorphic embedding
zbMATH Keywords: wheel
zbMATH Keywords: biwheel
MaRDI profile type: Publication
OpenAlex ID: W2122588376
cites work: Characterization and Recognition of Partial 3-Trees
cites work: Matroid 4-connectivity: A deletion-contraction theorem
cites work: Über einen Satz von K.Wagner zum Vierfarbenproblem
cites work: Zur Klassifikation der endlichen Graphen nach H. Hadwiger und K. Wagner
cites work: Homomorphiebasen von Graphenmengen
cites work: On possible counterexamples to Negami's planar cover conjecture
cites work: Q3758870
cites work: The spherical genus and virtually planar graphs
cites work: The structure of quasi 4-connected graphs
cites work: Minimal Cyclic-4-Connected Graphs
cites work: The structure of graphs not topologically containing the Wagner graph
cites work: Cyclically five-connected cubic graphs
cites work: Decomposition of regular matroids
cites work: Q3284374
cites work: Q5766469
cites work: Bemerkungen zu Hadwigers Vermutung
DOI: 10.1006/JCTB.2001.2089
Recommended article: Typical subgraphs of 3- and 4-connected graphs
Recommended article: Internally 4-connected graphs with no \(\{\text{cube}, V_8\}\)-minor
Recommended article: Q4281642
Recommended article: Q5422997
Recommended article: Odd \(K_{3,3}\) subdivisions in bipartite graphs
Recommended article: Minimally 3-connected graphs
Recommended article: Nonseparating K4‐subdivisions in graphs of minimum degree at least 4
Recommended article: Minimal Cyclic-4-Connected Graphs
Recommended article: On the decomposition of a 3-connected graph into cyclically 4-edge-connected components
Recommended article: Q4263662
description: scientific article; zbMATH DE number 1843822