Graph Theory » Basic G.T. » Matchings

Petersen graph conjecture ★

Author(s): Mkrtchyan; Petrosyan

Conjecture   Let G be a connected bridgeless cubic graph any 2-factor of which is comprised of cycles of the length five. Then G is the Petersen graph.

Keywords:

Posted by vahanmkrtchyan2002
updated November 25th, 2007
1 comment
Graph Theory » Coloring » Vertex coloring

Coloring squares of hypercubes ★★

Author(s): Wan

If $ G $ is a simple graph, we let $ G^{(2)} $ denote the simple graph with vertex set $ V(G) $ and two vertices adjacent if they are distance $ \le 2 $ in $ G $.

Conjecture   $ \chi(Q_d^{(2)}) = 2^{ \lfloor \log_2 d \rfloor + 1} $.

Keywords: coloring; hypercube

Posted by mdevos
updated December 10th, 2008
1 comment