Excluding a Weakly 4-connected Minor
type: CreativeWork
description: A 3-connected graph $G$ is called weakly 4-connected if min $(|E(G_1)|, |E(G_2)|) \leq 4$ holds for all 3-separations $(G_1,G_2)$ of $G$. A 3-connected graph $G$ is called quasi 4-connected if min $(|V(G_1)|, |V(G_2)|) \leq 4$. We first discuss how to decompose a 3-connected graph into quasi 4-connected components. We will establish a chain theorem which will allow us to easily generate the set of all quasi 4-connected graphs. Finally, we will apply these results to characterizing all graphs which do not contain the Pyramid as a minor, where the Pyramid is the weakly 4-connected graph obtained by performing a $\Delta Y$ transformation to the octahedron. This result can be used to show an interesting characterization of quasi 4-connected, outer-projective graphs.
abstract: A 3-connected graph $G$ is called weakly 4-connected if min $(|E(G_1)|, |E(G_2)|) \leq 4$ holds for all 3-separations $(G_1,G_2)$ of $G$. A 3-connected graph $G$ is called quasi 4-connected if min $(|V(G_1)|, |V(G_2)|) \leq 4$. We first discuss how to decompose a 3-connected graph into quasi 4-connected components. We will establish a chain theorem which will allow us to easily generate the set of all quasi 4-connected graphs. Finally, we will apply these results to characterizing all graphs which do not contain the Pyramid as a minor, where the Pyramid is the weakly 4-connected graph obtained by performing a $\Delta Y$ transformation to the octahedron. This result can be used to show an interesting characterization of quasi 4-connected, outer-projective graphs.
author: D'souza, Kimberly Sevin
keywords: graph theory, graph minors, graph decomposition, Pyramid graph
date published: 2016-01-01T08:00:00Z
date modified: 2026-07-24T02:59:22Z
provider: Lousiana State University
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Mathematics

PropertyValue
property ID: DOI
value: 10.31390/gradschool_dissertations.1368