Article ID Journal Published Year Pages File Type
4656751 Journal of Combinatorial Theory, Series B 2016 21 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,