A chain theorem for 4-connected graphs

作者：Qin, Chengfu^*; Ding, Guoli

来源：Journal of Combinatorial Theory - Series B, 2019, 134: 341-349.

DOI：10.1016/j.jctb.2018.07.005

• 4-connected graphs
• Chain theorem
• Contractible edge
• Nonplanar graphs

A sequence of 4-connected graphs G(0), G(1), ... , G(n), is called a (G(0), G(n))-chain if each G(i) (i < n) has an edge e(i) such that G(i)/e(i) = G(i+1). A classical result of Martinov states that for every 4-connected graph G there exists a (G, H)-chain such that H is an element of C boolean OR L, where C = {C-n(2) : n >= 5} and L = {L : L be the line graph of a cyclically 4-edge-connected cubic graph}. This result is strengthened in this paper as follows. Suppose G is 4-connected and G is not an element of C boolean OR L. Then there exists a (G, C-6(2))-chain if G is planar and a (G, C-5(2))-chain if G is nonplanar.

• 出版日期2019-1
• 单位南宁师范大学