Isolating highly connected induced subgraphs

Irena Penev

Ancienne Post-doctorante – ENS Lyon – LIP 

→ du 01/09/2013 au 31/08/2015

Abstract: We prove that every graph G of minimum degree at least 2k2 contains a (k+1)-connected induced subgraph H such that at most 2k2-1 vertices of H have a neighbor in V(G)-V(H). This is related to a classical result of Mader that every graph of average degree at least 4k has a (k+1)-connected subgraph. We also show that every graph of chromatic number greater than max{c+2k-2,2k2} has a (k+1) connected induced subgraph of chromatic number greater than c. This improves a result of Alon, Kleitman, Saks, Seymour, and Thomassen from 1987.

Keywords : induced subgraph, connectivity, coloring

 

Télécharger le poster [PDF – 331 Ko]

>> En savoir plus sur cette ancienne post-doctorante