Mader (1972) proved that every graph of average degree at least 4k contains a (k+1)-connected subgraph, and Alon, Kleitman, Saks, Seymour, and Thomassen (1987) proved that every graph of chromatic number greater than \max\{c+10k^2,100k^3\} contains a (k+1)-connected subgraph of chromatic number at least c. We prove a variant of Mader’s theorem (with stronger hypotheses and a stronger conclusion), and we improve the bound in the theorem of Alon et al.
Given a graph G, \delta(G) is the minimum degree of G. If H is an induced subgraph of G, then \partial_G(H) is the set of all vertices of H that have a neighbor in V(G) \setminus V(H). Our main results are the following two theorems.
Theorem 1. Let k be a positive integer, and let G be a graph. If \delta_G(G) > 2k^2-1, then G contains a (k+1)-connected induced subgraph H such that \partial_G(H) \subsetneqq V(H) and |\partial_G(H)| \leq 2k^2-1.
Theorem 2. Let k and c be positive integers, and let G be a graph such that \chi(G) > \max\{c+2k-2,2k^2\}. Then G contains a (k+1)-connected induced subgraph of chromatic number greater than c.
A {\em cut-partition} of a graph G is a partition (A,B,C) of V(G) such that A and B are non-empty (C may possibly be empty), and there are no edges between A and B. Theorem 1 is an immediate corollary of a certain technical lemma, which roughly states that if the minimum degree of a graph G is greater than 2k^2-1, then either G is (k+1)-connected, or G admits a cut-partition (A,B,C) such that G[A \cup C] is (k+1)-connected, |C| \leq 2k^2-1, and at most 2k-1 vertices of C have more than k neighbors in B. The precise statement of this lemma, as well as an outline of its proof, will be given in the talk. This lemma is also one of the main ingredients of the proof of Theorem 2.
This is joint work with Stephan Thomasse and Nicolas Trotignon.
