# Conditions for $k$-connected graphs to have a $k$-contractible edge

###
Kiyoshi Ando

Natinal Institute of Informatics, JST ERATO Kawarabayashi Large Graph Project

PDF

**Minisymposium:**
GENERAL SESSION TALKS

**Content:**
An edge of a $k$-connected graph is said to be $k$-contractible if the contraction of it results a $k$-connected graph.
When $k\le 3$, each $k$-connected graph on more then $k+1$ vertices has a $k$-contractible edge.
When $k\ge 4$, there are infinitely many $k$-connected graphs with no $k$-contractible edge.
Hence, if $k\ge 4$, we can not expect the existence of a $k$-contractible edge in a $k$-connected graph
with no condition.
We say `$k$-sufficient condition' for a condition for a $k$-connected graph to have a $k$-contractible edge.
In this talk, we give some $k$-sufficient conditions involving forbidden subgraphs, one of which is an extension of a Kawarabayashi's result.