A chain theorem for 4-connected 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. (C) 2018 Elsevier Inc. All rights reserved.