Graph Theory » Hypergraphs

¿Are critical k-forests tight? ★★

Author(s): Strausz

Conjecture  

Let $ H $ be a $ k $-uniform hypergraph. If $ H $ is a critical $ k $-forest, then it is a $ k $-tree.

Keywords: heterochromatic number

Posted by Dino
updated May 5th, 2014
1 comment
Graph Theory » Basic G.T. » Cycles

Bigger cycles in cubic graphs ★★

Author(s):

Problem   Let $ G $ be a cyclically 4-edge-connected cubic graph and let $ C $ be a cycle of $ G $. Must there exist a cycle $ C' \neq C $ so that $ V(C) \subseteq V(C') $?

Keywords: cubic; cycle

Posted by mdevos
updated September 4th, 2009
1 comment
Graph Theory » Basic G.T. » Matchings

The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

Conjecture   Every bridgeless cubic graph has two perfect matchings $ M_1 $, $ M_2 $ so that $ M_1 \cap M_2 $ does not contain an odd edge-cut.

Keywords: cubic; nowhere-zero flow; perfect matching

Posted by mdevos
updated August 30th, 2007
add new comment