Graph Theory

Switching reconstruction conjecture ★★

Author(s): Stanley

Conjecture   Every simple graph on five or more vertices is switching-reconstructible.

Keywords: reconstruction

Posted by fhavet
updated March 7th, 2013
add new comment
Graph Theory » Topological G.T.

Every 4-connected toroidal graph has a Hamilton cycle ★★

Author(s): Grunbaum; Nash-Williams

Conjecture   Every 4-connected toroidal graph has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 7th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Steinberg's conjecture ★★★★

Author(s):

Conjecture   Every planar graph without 4-cycles and 5-cycles is 3-colourable.

Keywords:

Posted by fhavet
updated September 12th, 2016
1 comment
Graph Theory » Coloring » Vertex coloring

Acyclic list colouring of planar graphs. ★★★

Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena

Conjecture   Every planar graph is acyclically 5-choosable.

Keywords:

Posted by fhavet
updated March 7th, 2013
add new comment
Graph Theory » Coloring » Vertex coloring

Earth-Moon Problem ★★

Author(s): Ringel

Problem   What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?

Keywords:

Posted by fhavet
updated March 6th, 2013
add new comment