connectivity


Forcing a $K_6$-minor ★★

Author(s): Barát ; Joret; Wood

\begin{conjecture} Every graph with minimum degree at least 7 contains a $K_6$-minor. \end{conjecture}

\begin{conjecture} Every 7-connected graph contains a $K_6$-minor. \end{conjecture}

Keywords: connectivity; graph minors

Chords of longest cycles ★★★

Author(s): Thomassen

\begin{conjecture} If $G$ is a 3-connected graph, every longest cycle in $G$ has a chord. \end{conjecture}

Keywords: chord; connectivity; cycle

Jorgensen's Conjecture ★★★

Author(s): Jorgensen

\begin{conjecture} Every 6-\Def[connected]{connectivity (graph theory)} graph without a \Def[$K_6$]{complete graph} \Def[minor]{minor (graph theory)} is apex (planar plus one vertex). \end{conjecture}

Keywords: connectivity; minor

Highly connected graphs with no K_n minor ★★★

Author(s): Thomas

\begin{problem} Is it true for all $n \ge 0$, that every sufficiently large $n$-\Def[connected]{connectivity (graph theory)} graph without a \Def[$K_n$]{complete graph} \Def[minor]{minor (graph theory)} has a set of $n-5$ vertices whose deletion results in a \Def{planar graph}? \end{problem}

Keywords: connectivity; minor

Syndicate content