Graph Theory » Basic G.T. » Matchings

Matchings extend to Hamiltonian cycles in hypercubes ★★

Author(s): Ruskey; Savage

Question   Does every matching of hypercube extend to a Hamiltonian cycle?

Keywords: Hamiltonian cycle; hypercube; matching

Posted by Jirka
updated September 28th, 2007
add new comment
Graph Theory » Topological G.T. » Drawings

Linear Hypergraphs with Dimension 3 ★★

Author(s): de Fraysseix; Ossona de Mendez; Rosenstiehl

Conjecture   Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.

Keywords: Hypergraphs

Posted by taxipom
updated September 26th, 2007
add new comment

Editorial policy

To ensure that the Garden is a high quality resource, we reserve the right to move submitted open problems to an alternate location on our site. These Second tier problems can be found by clicking the More link in the Navigate menu. When considering submissions, we take into account the value of the question, its relevance, and clarity of the exposition. Still, some of these Second tier problems can be an interesting exercise, or a worthy (but inadequately presented) question. Our editors (called greenthumbs) are listed below.

    Greenthumbs
  • Matt DeVos
  • Robert Samal