Open Problems


TitleAuthor(s)sort iconImp.¹Rec.²Area » Topic » SubtopicPosted by
P vs. BPPFolklore✭✭✭0Theoretical Comp. Sci. » Complexity » DerandomizationCharles R Great...
Algorithm for graph homomorphismsFomin; Heggernes; Kratsch✭✭0Graph Theory » Coloring » Homomorphismsjfoniok
Slice-ribbon problemFox✭✭✭✭0Topologyrybu
Complete bipartite subgraphs of perfect graphsFox✭✭0Graph Theory » Basic G.T.mdevos
Long rainbow arithmetic progressionsFox; Jungic; Mahdian; Nesetril; Radoicic✭✭0Combinatoricsvjungic
Frankl's union-closed sets conjectureFrankl✭✭0Graph Theory » Hypergraphstchow
Subgroup formed by elements of order dividing nFrobenius✭✭0Group Theorydlh12
Do any three longest paths in a connected graph have a vertex in common? Gallai✭✭0Graph Theoryfhavet
Decomposing a connected graph into paths.Gallai✭✭✭0Graph Theory » Basic G.T. » Pathsfhavet
Are vertex minor closed classes chi-bounded?Geelen✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Sum of prime and semiprime conjectureGeoffrey Marnell✭✭0Number Theoryprinceps
Hamiltonian cycles in line graphs of infinite graphsGeorgakopoulos✭✭0Graph Theory » Infinite GraphsRobert Samal
Hamiltonian cycles in powers of infinite graphsGeorgakopoulos✭✭0Graph Theory » Infinite GraphsRobert Samal
End-Devouring RaysGeorgakopoulos1Graph Theory » Infinite GraphsAgelos
Geodesic cycles and Tutte's TheoremGeorgakopoulos; Sprüssel✭✭1Graph Theory » Basic G.T. » CyclesAgelos
Special PrimesGeorge BALAN1Number Theorymaththebalans
Circular coloring triangle-free subcubic planar graphsGhebleh; Zhu✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Giuga's Conjecture on PrimalityGiuseppe Giuga✭✭0Number Theoryprinceps
A conjecture on iterated circumcentresGoddyn✭✭1Geometrymdevos
Complexity of square-root sumGoemans✭✭0Theoretical Comp. Sci. » Complexityabie
Goldbach conjectureGoldbach✭✭✭✭0Number Theory » Additive N.T.Benschop
Goldberg's conjectureGoldberg✭✭✭0Graph Theory » Coloring » Edge coloringmdevos
What is the smallest number of disjoint spanning trees made a graph HamiltonianGoldengorin✭✭0Graph Theory » Extremal G.T.boris
Length of surreal productGonshor1CombinatoricsLukáš Lánský
Unsolvability of word problem for 2-knot complementsGordon✭✭✭0Topologyrybu
Combinatorial covering designsGordon; Mills; Rödl; Schönheim0Combinatorics » DesignsPseudonym
General position subsetsGowers✭✭0GeometryDavid Wood
Graham's conjecture on tree reconstructionGraham✭✭0Graph Theory » Basic G.T.mdevos
Divisibility of central binomial coefficientsGraham✭✭1Number Theory » Combinatorial N.T.maxal
Pebbling a cartesian productGraham✭✭✭0Graph Theorymdevos
Termination of the sixth Goodstein SequenceGraham0Logicmdevos
MSO alternation hierarchy over picturesGrandjean✭✭0Logic » Finite Model Theorydberwanger
Universal Steiner triple systemsGrannell; Griggs; Knor; Skoviera✭✭0Graph Theory » Coloring » Edge coloringmacajova
inverse of an integer matrixGregory✭✭0Algebralvoyster
Grunbaum's ConjectureGrunbaum✭✭✭0Graph Theory » Topological G.T. » Coloringmdevos
4-regular 4-chromatic graphs of high girthGrunbaum✭✭0Graph Theory » Coloringmdevos
Every 4-connected toroidal graph has a Hamilton cycleGrunbaum; Nash-Williams✭✭0Graph Theory » Topological G.T.fhavet
Laplacian Degrees of a GraphGuo✭✭0Graph Theory » Algebraic G.T.Robert Samal
Graphs with a forbidden induced tree are chi-boundedGyarfas✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
The circular embedding conjectureHaggard✭✭✭0Graph Theory » Basic G.T. » Cyclesmdevos
Decomposing an eulerian graph into cycles.Hajós✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
Edge Reconstruction ConjectureHarary✭✭✭0Graph Theorymelch
Large acyclic induced subdigraph in a planar oriented graph.Harutyunyan✭✭0Graph Theory » Directed Graphsfhavet
Fractional HadwigerHarvey; Reed; Seymour; Wood✭✭1Graph TheoryDavid Wood
Chromatic Number of Common GraphsHatami; Hladký; Kráľ; Norine; Razborov✭✭0Graph TheoryDavid Wood
Erdős-Posa property for long directed cyclesHavet; Maia✭✭0Graph Theory » Directed Graphsfhavet
Almost all non-Hamiltonian 3-regular graphs are 1-connectedHaythorpe✭✭1Graph Theory » Basic G.T.mhaythorpe
Hedetniemi's ConjectureHedetniemi✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Inverse Galois ProblemHilbert✭✭✭✭0Group Theorytchow
2-colouring a graph without a monochromatic maximum cliqueHoang; McDiarmid✭✭0Graph Theory » Coloring » Vertex coloringJon Noel
Syndicate content