Home

Open Problems


TitleAuthor(s)Imp.¹Rec.²Area » Topic » Subtopicsort iconPosted by
The Berge-Fulkerson conjectureBerge; Fulkerson✭✭✭✭0Graph Theory » Basic G.T. » Matchingsmdevos
The intersection of two perfect matchingsMacajova; Skoviera✭✭0Graph Theory » Basic G.T. » Matchingsmdevos
Matchings extend to Hamiltonian cycles in hypercubesRuskey; Savage✭✭1Graph Theory » Basic G.T. » MatchingsJirka
Random stable roommatesMertens✭✭0Graph Theory » Basic G.T. » Matchingsmdevos
Cycle double cover conjectureSeymour; Szekeres✭✭✭✭0Graph Theory » Basic G.T. » Cyclesmdevos
The circular embedding conjectureHaggard✭✭✭0Graph Theory » Basic G.T. » Cyclesmdevos
(m,n)-cycle coversCelmins; Preissmann✭✭✭0Graph Theory » Basic G.T. » Cyclesmdevos
Faithful cycle coversSeymour✭✭✭0Graph Theory » Basic G.T. » Cyclesmdevos
Decomposing eulerian graphs✭✭✭0Graph Theory » Basic G.T. » Cyclesmdevos
Barnette's ConjectureBarnette✭✭✭0Graph Theory » Basic G.T. » CyclesRobert Samal
r-regular graphs are not uniquely hamiltonian.Sheehan✭✭✭0Graph Theory » Basic G.T. » CyclesRobert Samal
Hamiltonian cycles in line graphsThomassen✭✭✭0Graph Theory » Basic G.T. » CyclesRobert Samal
Geodesic cycles and Tutte's TheoremGeorgakopoulos; Sprüssel✭✭1Graph Theory » Basic G.T. » CyclesAgelos
Bigger cycles in cubic graphs✭✭0Graph Theory » Basic G.T. » Cyclesmdevos
Jones' conjectureKloks; Lee; Liu✭✭0Graph Theory » Basic G.T. » Cyclescmlee
Chords of longest cyclesThomassen✭✭✭0Graph Theory » Basic G.T. » Cyclesmdevos
Short cycle coversAlon; Tarsi✭✭0Graph Theory » Basic G.T. » CyclesRobert Samal
Middle levels problemErdos✭✭0Graph Theory » Basic G.T. » Cyclestchow
Hamiltonicity of Cayley graphsRapaport-Strasser✭✭✭1Graph Theory » Basic G.T. » Cyclestchow
Strong 5-cycle double cover conjectureArthur; Hoffmann-Ostenhof✭✭✭1Graph Theory » Basic G.T. » Cyclesarthur
Decomposing an eulerian graph into cycles.Hajós✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour.Sabidussi✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
Every prism over a 3-connected planar graph is hamiltonian.Kaiser; Král; Rosenfeld; Ryjácek; Voss✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
4-connected graphs are not uniquely hamiltonianFleischner✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
Hamilton decomposition of prisms over 3-connected cubic planar graphsAlspach; Rosenfeld✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
Partitioning edge-connectivityDeVos✭✭0Graph Theory » Basic G.T. » Connectivitymdevos
Graham's conjecture on tree reconstructionGraham✭✭0Graph Theory » Basic G.T.mdevos
Nearly spanning regular subgraphsAlon; Mubayi✭✭✭0Graph Theory » Basic G.T.mdevos
Complete bipartite subgraphs of perfect graphsFox✭✭0Graph Theory » Basic G.T.mdevos
Asymptotic Distribution of Form of Polyhedra Rüdinger✭✭0Graph Theory » Basic G.T.andreasruedinger
Domination in cubic graphsReed✭✭0Graph Theory » Basic G.T.mdevos
Friendly partitionsDeVos✭✭0Graph Theory » Basic G.T.mdevos
Subgraph of large average degree and large girth.Thomassen✭✭0Graph Theory » Basic G.T.fhavet
57-regular Moore graph?Hoffman; Singleton✭✭✭0Graph Theory » Algebraic G.T.mdevos
Hamiltonian paths and cycles in vertex transitive graphsLovasz✭✭✭0Graph Theory » Algebraic G.T.mdevos
Triangle free strongly regular graphs✭✭✭0Graph Theory » Algebraic G.T.mdevos
Half-integral flow polynomial valuesMohar✭✭0Graph Theory » Algebraic G.T.mohar
Ramsey properties of Cayley graphsAlon✭✭✭0Graph Theory » Algebraic G.T.mdevos
Laplacian Degrees of a GraphGuo✭✭0Graph Theory » Algebraic G.T.Robert Samal
Cores of strongly regular graphsCameron; Kazanidis✭✭✭0Graph Theory » Algebraic G.T.mdevos
Does the chromatic symmetric function distinguish between trees?Stanley✭✭0Graph Theory » Algebraic G.T.mdevos
Pebbling a cartesian productGraham✭✭✭0Graph Theorymdevos
Reconstruction conjectureKelly; Ulam✭✭✭✭0Graph Theoryzitterbewegung
Edge Reconstruction ConjectureHarary✭✭✭0Graph Theorymelch
Book Thickness of SubdivisionsBlankenship; Oporowski✭✭1Graph TheoryDavid Wood
Shannon capacity of the seven-cycle✭✭✭0Graph Theorytchow
Number of Cliques in Minor-Closed ClassesWood✭✭0Graph TheoryDavid Wood
Shuffle-Exchange Conjecture (graph-theoretic form)Beneš; Folklore; Stone✭✭✭0Graph TheoryVadim Lioubimov
Separators in string graphsFox; Pach; Tóth✭✭0Graph Theorycibulka
Odd cycles and low oddness✭✭0Graph TheoryGagik

Imp.¹: Importance (Low ✭, Medium ✭✭, High ✭✭✭, Outstanding ✭✭✭✭)
Rec.²: Recommended for undergraduates.

Note: Resolved problems from this section may be found in Solved problems.

Syndicate content