Document Type
Lecture
Publication Date
2-3-2016
Abstract
Let C = C2 n :n 5 and let L= G:G is the line graph of an internally 4-connected cubic graph. A classical result of Martinov states that every 4-connected graph G can be constructed from graphs in C L by repeatedly splitting vertices. In this paper we prove that, in fact, G can be constructed from C2 5 or C2 6 in the same way, unless G belongs to C L. Moreover, if G is nonplanar then G can be constructed from C2 5. A G is called critical if G is internally 4-connected but G/e and G\e are not for all e E(G). A result of J. Oxley states there are nineteen operations that reduce G to a critical internally 4-connected minor unless G is ladder, m¨ obius ladder, double wheel or terrahawk. We prove that there are ten operations that reduce G to a critical internally 4-connected minor unless G is ladder, m¨obius ladder, double wheel, terrahawk, the line graph of 3-connected cubic graph. Moreover, there are examples show that eight of them are necessary. This is joint work with Guoli Ding.
Relational Format
presentation
Recommended Citation
Qin, Chengfu, "The chain theorem of 4-connected graphs" (2016). Combinatorics Seminar. 29.
https://egrove.olemiss.edu/math_combinatorics/29
