Home

Open Problems


TitleAuthor(s)Imp.¹Rec.²Area » Topic » Subtopicsort iconPosted by
Decomposing a connected graph into paths.Gallai✭✭✭0Graph Theory » Basic G.T. » Pathsfhavet
Partition of a cubic 3-connected graphs into paths of length 2.Kelmans✭✭0Graph Theory » Basic G.T. » Pathsfhavet
Linial-Berge path partition dualityBerge; Linial✭✭✭0Graph Theory » Coloringberger
Three-chromatic (0,2)-graphsPayan✭✭0Graph Theory » ColoringGordon Royle
Total Colouring ConjectureBehzad✭✭✭0Graph Theory » ColoringIradmusa
4-regular 4-chromatic graphs of high girthGrunbaum✭✭0Graph Theory » Coloringmdevos
Coloring the union of degenerate graphsTarsi✭✭0Graph Theory » Coloringfhavet
List Total Colouring ConjectureBorodin; Kostochka; Woodall✭✭0Graph Theory » ColoringJon Noel
Petersen coloring conjectureJaeger✭✭✭0Graph Theory » Coloring » Edge coloringmdevos
Packing T-joinsDeVos✭✭0Graph Theory » Coloring » Edge coloringmdevos
Acyclic edge-colouringFiamcik✭✭0Graph Theory » Coloring » Edge coloringmdevos
A generalization of Vizing's Theorem?Rosenfeld✭✭0Graph Theory » Coloring » Edge coloringmdevos
List colorings of edge-critical graphsMohar✭✭0Graph Theory » Coloring » Edge coloringRobert Samal
Universal Steiner triple systemsGrannell; Griggs; Knor; Skoviera✭✭0Graph Theory » Coloring » Edge coloringmacajova
Edge list coloring conjecture✭✭✭0Graph Theory » Coloring » Edge coloringtchow
Seymour's r-graph conjectureSeymour✭✭✭0Graph Theory » Coloring » Edge coloringmdevos
Goldberg's conjectureGoldberg✭✭✭0Graph Theory » Coloring » Edge coloringmdevos
Strong edge colouring conjectureErdos; Nesetril✭✭0Graph Theory » Coloring » Edge coloringfhavet
Cores of Cayley graphsSamal✭✭0Graph Theory » Coloring » HomomorphismsRobert Samal
Pentagon problemNesetril✭✭✭0Graph Theory » Coloring » HomomorphismsRobert Samal
Mapping planar graphs to odd cyclesJaeger✭✭✭0Graph Theory » Coloring » Homomorphismsmdevos
Weak pentagon problemSamal✭✭0Graph Theory » Coloring » HomomorphismsRobert Samal
Algorithm for graph homomorphismsFomin; Heggernes; Kratsch✭✭0Graph Theory » Coloring » Homomorphismsjfoniok
Circular choosability of planar graphsMohar✭0Graph Theory » Coloring » Homomorphismsrosskang
Graceful Tree Conjecture✭✭✭0Graph Theory » Coloring » Labelingkintali
Good Edge LabelingsAraújo; Cohen; Giroire; Havet✭✭0Graph Theory » Coloring » LabelingDOT
5-flow conjectureTutte✭✭✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
4-flow conjectureTutte✭✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
3-flow conjectureTutte✭✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
Jaeger's modular orientation conjectureJaeger✭✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
Bouchet's 6-flow conjectureBouchet✭✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
The three 4-flows conjectureDeVos✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
A homomorphism problem for flowsDeVos✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
Real roots of the flow polynomialWelsh✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
Unit vector flowsJain✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
Antichains in the cycle continuous orderDeVos✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
Circular flow number of regular class 1 graphsSteffen✭✭0Graph Theory » Coloring » Nowhere-zero flowsEckhard Steffen
Strong colorabilityAharoni; Alon; Haxell✭✭✭0Graph Theory » Coloring » Vertex coloringberger
Reed's omega, delta, and chi conjectureReed✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Circular coloring triangle-free subcubic planar graphsGhebleh; Zhu✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Oriented chromatic number of planar graphs✭✭0Graph Theory » Coloring » Vertex coloringRobert Samal
Coloring and immersionAbu-Khzam; Langston✭✭✭1Graph Theory » Coloring » Vertex coloringmdevos
Coloring the Odd Distance GraphRosenfeld✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Partial List ColoringAlbertson; Grossman; Haas✭✭✭0Graph Theory » Coloring » Vertex coloringIradmusa
Partial List ColoringIradmusa✭✭✭0Graph Theory » Coloring » Vertex coloringIradmusa
Hedetniemi's ConjectureHedetniemi✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Counting 3-colorings of the hex latticeThomassen✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Circular colouring the orthogonality graphDeVos; Ghebleh; Goddyn; Mohar; Naserasr✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Double-critical graph conjectureErdos; Lovasz✭✭0Graph Theory » Coloring » Vertex coloringDFR
Bounding the chromatic number of triangle-free graphs with fixed maximum degreeKostochka; Reed✭✭0Graph Theory » Coloring » Vertex coloringAndrew King

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

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

Syndicate content