Graph-theory open problems

Basic Graph Theory

subject tag · 39 problems

Title Source Status Imp. Posted
Cycle double cover conjecture opg partial ★★★★ 2007-03-07
The Berge-Fulkerson conjecture opg partial ★★★★ 2007-03-07
Decomposing a connected graph into paths. opg partial ★★★ 2013-03-04
Strong 5-cycle double cover conjecture opg partial ★★★ 2010-08-03
Hamiltonicity of Cayley graphs opg partial ★★★ 2008-09-25
Nearly spanning regular subgraphs opg open ★★★ 2008-05-22
Seagull problem opg partial ★★★ 2008-01-06
(m,n)-cycle covers opg partial ★★★ 2007-03-07
Barnette's Conjecture opg partial ★★★ 2007-06-12
Chords of longest cycles opg partial ★★★ 2007-11-12
Decomposing eulerian graphs opg partial ★★★ 2007-03-07
Faithful cycle covers opg open ★★★ 2007-03-07
Hamiltonian cycles in line graphs opg partial ★★★ 2007-07-24
Highly connected graphs with no K_n minor opg partial ★★★ 2007-03-10
Jorgensen's Conjecture opg partial ★★★ 2007-03-10
r-regular graphs are not uniquely hamiltonian. opg partial ★★★ 2007-07-24
The circular embedding conjecture opg partial ★★★ 2007-03-07
Forcing a 2-regular minor opg solved ★★ 2014-03-16
4-connected graphs are not uniquely hamiltonian opg open ★★ 2013-03-11
Almost all non-Hamiltonian 3-regular graphs are 1-connected opg open ★★ 2013-08-23
Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour. opg open ★★ 2013-03-04
Decomposing an eulerian graph into cycles. opg partial ★★ 2013-03-04
Every prism over a 3-connected planar graph is hamiltonian. opg disproved ★★ 2013-03-11
Hamilton decomposition of prisms over 3-connected cubic planar graphs opg partial ★★ 2013-03-12
Kriesell's Conjecture opg partial ★★ 2013-08-25
Partition of a cubic 3-connected graphs into paths of length 2. opg open ★★ 2013-03-04
Subgraph of large average degree and large girth. opg partial ★★ 2013-03-05
Forcing a $K_6$-minor opg partial ★★ 2012-01-16
Asymptotic Distribution of Form of Polyhedra opg open ★★ 2009-05-09
Domination in cubic graphs opg open ★★ 2009-08-19
Friendly partitions opg partial ★★ 2009-11-08
Complete bipartite subgraphs of perfect graphs opg open ★★ 2008-06-17
Random stable roommates opg partial ★★ 2008-02-26
Geodesic cycles and Tutte's Theorem opg open ★★ 2007-08-04
Graham's conjecture on tree reconstruction opg partial ★★ 2007-03-18
Jones' conjecture opg partial ★★ 2007-10-09
Matchings extend to Hamiltonian cycles in hypercubes opg partial ★★ 2007-09-28
Partitioning edge-connectivity opg open ★★ 2007-03-07
The intersection of two perfect matchings opg partial ★★ 2007-08-30