Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656751 | Journal of Combinatorial Theory, Series B | 2016 | 21 Pages |
A well-known conjecture of Thomassen says that every (a+b+1)(a+b+1)-connected graph with a≥ba≥b can be decomposed into two parts A and B such that A is a-connected and B is b -connected. The case b=2b=2 is settled by Thomassen himself, but the conjecture is still open for b≥3b≥3.Motivated by this, we prove that every k-connected graph G (with k≥4k≥4) has a subgraph M such that either1.M is 3-connected with at most 5 vertices (thus G−V(M)G−V(M) is (k−5)(k−5)-connected), or2.M is an induced cycle such that G−V(C)G−V(C) is (k−2)(k−2)-connected.This result improves previous known results by Egawa and Kawarabayashi, respectively.Our result is also related to results and questions of Mader concerning critically k-connected graphs. We partially answer the question of Mader in 1988.