A new forbidden subgraph for 5-contractible edges

摘要

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A graph H is said to be a forbidden subgraph for k-contractible edges if every k-connected graph with no subgraph isomorphic to H has a k-contractible edge. Kawarabayashi showed that if k is an odd integer such that k >= 5, then K-1 + (P-3 boolean OR K-2) is a forbidden subgraph for k-contractible edges. We present a new forbidden subgraph for 5-contractible edges which has K-1 + (P-3 boolean OR K-2) as a subgraph. This is an extension of the previous result in 5-connected case. (C) 2020 Elsevier B.V. All rights reserved.