Home » Keyword index

minor


Graph Theory

Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

Question   Is there a constant $ c $ such that every $ n $-vertex $ K_t $-minor-free graph has at most $ c^tn $ cliques?

Keywords: clique; graph; minor

Posted by David Wood
updated October 12th, 2009
add new comment
Graph Theory » Basic G.T. » Minors

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

Posted by mdevos
updated January 6th, 2008
add new comment
Graph Theory » Infinite Graphs

Seymour's self-minor conjecture ★★★

Author(s): Seymour

Conjecture   Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor

Posted by mdevos
updated April 15th, 2010
2 comments
Graph Theory » Topological G.T. » Genus

Consecutive non-orientable embedding obstructions ★★★

Author(s):

Conjecture   Is there a graph $ G $ that is a minor-minimal obstruction for two non-orientable surfaces?

Keywords: minor; surface

Posted by Bruce Richter
updated September 15th, 2010
2 comments
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
Graph Theory » Coloring » Nowhere-zero flows

4-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Keywords: minor; nowhere-zero flow; Petersen graph

Posted by mdevos
updated April 12th, 2009
2 comments
Syndicate content