Open AccessA Chain Theorem for $3^+$-Connected Graphs
Author(s) -
Guoli Ding,
Liu Cheng
Publication year - 2012
Publication title -
siam journal on discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.843
H-Index - 66
eISSN - 1095-7146
pISSN - 0895-4801
DOI - 10.1137/110834408
Subject(s) - combinatorics , mathematics , graph minor , discrete mathematics , graph , line graph , block graph , connectivity , pathwidth , voltage graph
A 3-connected graph is called $3^+$-connected if it has no 3-separation that separates a “large” fan or $K_{3,n}$ from the rest of the graph. It is proved in this paper that except for $K_4$, every $3^+$-connected graph has a $3^+$-connected proper minor that is at most two edges away from the original graph. This result is used to characterize $Q$-minor-free graphs, where $Q$ is obtained from the cube by contracting an edge.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom