Home » Keyword index

connectivity


Graph Theory » Basic G.T. » Minors

Forcing a $K_6$-minor ★★

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

Conjecture   Every graph with minimum degree at least 7 contains a $ K_6 $-minor.
Conjecture   Every 7-connected graph contains a $ K_6 $-minor.

Keywords: connectivity; graph minors

Posted by David Wood
updated January 16th, 2012
add new comment
Graph Theory » Basic G.T. » Cycles

Chords of longest cycles ★★★

Author(s): Thomassen

Conjecture   If $ G $ is a 3-connected graph, every longest cycle in $ G $ has a chord.

Keywords: chord; connectivity; cycle

Posted by mdevos
updated October 14th, 2023
1 comment
Graph Theory » Basic G.T. » Minors

Jorgensen's Conjecture ★★★

Author(s): Jorgensen

Conjecture   Every 6-connected graph without a $ K_6 $ minor is apex (planar plus one vertex).

Keywords: connectivity; minor

Posted by mdevos
updated March 10th, 2007
add new comment
Graph Theory » Basic G.T. » Minors

Highly connected graphs with no K_n minor ★★★

Author(s): Thomas

Problem   Is it true for all $ n \ge 0 $, that every sufficiently large $ n $-connected graph without a $ K_n $ minor has a set of $ n-5 $ vertices whose deletion results in a planar graph?

Keywords: connectivity; minor

Posted by mdevos
updated March 10th, 2007
add new comment
Syndicate content