Home » Subject » Graph Theory

Basic Graph Theory


TitleAuthor(s)sort iconImp.¹Rec.²SubtopicPosted by
Hamiltonian cycles in line graphsThomassen✭✭✭0CyclesRobert Samal
Chords of longest cyclesThomassen✭✭✭0Cyclesmdevos
Subgraph of large average degree and large girth.Thomassen✭✭0fhavet
Highly connected graphs with no K_n minorThomas✭✭✭0Minorsmdevos
r-regular graphs are not uniquely hamiltonian.Sheehan✭✭✭0CyclesRobert Samal
Cycle double cover conjectureSeymour; Szekeres✭✭✭✭0Cyclesmdevos
Faithful cycle coversSeymour✭✭✭0Cyclesmdevos
Seagull problemSeymour✭✭✭0Minorsmdevos
Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour.Sabidussi✭✭0Cyclesfhavet
Matchings extend to Hamiltonian cycles in hypercubesRuskey; Savage✭✭1MatchingsJirka
Asymptotic Distribution of Form of Polyhedra Rüdinger✭✭0andreasruedinger
Domination in cubic graphsReed✭✭0mdevos
Hamiltonicity of Cayley graphsRapaport-Strasser✭✭✭1Cyclestchow
Random stable roommatesMertens✭✭0Matchingsmdevos
The intersection of two perfect matchingsMacajova; Skoviera✭✭0Matchingsmdevos
Jones' conjectureKloks; Lee; Liu✭✭0Cyclescmlee
Partition of a cubic 3-connected graphs into paths of length 2.Kelmans✭✭0Pathsfhavet
Every prism over a 3-connected planar graph is hamiltonian.Kaiser; Král; Rosenfeld; Ryjácek; Voss✭✭0Cyclesfhavet
Jorgensen's ConjectureJorgensen✭✭✭0Minorsmdevos
Decomposing an eulerian graph into cycles.Hajós✭✭0Cyclesfhavet
The circular embedding conjectureHaggard✭✭✭0Cyclesmdevos
Graham's conjecture on tree reconstructionGraham✭✭0mdevos
Geodesic cycles and Tutte's TheoremGeorgakopoulos; Sprüssel✭✭1CyclesAgelos
Decomposing a connected graph into paths.Gallai✭✭✭0Pathsfhavet
Complete bipartite subgraphs of perfect graphsFox✭✭0mdevos
4-connected graphs are not uniquely hamiltonianFleischner✭✭0Cyclesfhavet
Middle levels problemErdos✭✭0Cyclestchow
Partitioning edge-connectivityDeVos✭✭0Connectivitymdevos
Friendly partitionsDeVos✭✭0mdevos
(m,n)-cycle coversCelmins; Preissmann✭✭✭0Cyclesmdevos
Linial-Berge path partition dualityBerge; Linial✭✭✭0Pathsberger
The Berge-Fulkerson conjectureBerge; Fulkerson✭✭✭✭0Matchingsmdevos
Barnette's ConjectureBarnette✭✭✭0CyclesRobert Samal
Forcing a $K_6$-minorBarát ; Joret; Wood✭✭0MinorsDavid Wood
Strong 5-cycle double cover conjectureArthur; Hoffmann-Ostenhof✭✭✭1Cyclesarthur
Hamilton decomposition of prisms over 3-connected cubic planar graphsAlspach; Rosenfeld✭✭0Cyclesfhavet
Short cycle coversAlon; Tarsi✭✭0CyclesRobert Samal
Nearly spanning regular subgraphsAlon; Mubayi✭✭✭0mdevos
Decomposing eulerian graphs✭✭✭0Cyclesmdevos
Bigger cycles in cubic graphs✭✭0Cyclesmdevos

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

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

Syndicate content