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

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

Seagull problem ★★★

Author(s): Seymour

Conjecture   Every $ n $ vertex graph with no independent set of size $ 3 $ has a complete graph on $ \ge \frac{n}{2} $ vertices as a minor.

Keywords: coloring; complete graph; minor

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

Forcing a 2-regular minor ★★

Author(s): Reed; Wood

Conjecture   Every graph with average degree at least $ \frac{4}{3}t-2 $ contains every 2-regular graph on $ t $ vertices as a minor.

Keywords: minors


Syndicate content