Open Problems


TitleAuthor(s)Imp.¹sort iconRec.²Area » Topic » SubtopicPosted by
Shannon capacity of the seven-cycle✭✭✭0Graph Theorytchow
Refuting random 3SAT-instances on $O(n)$ clauses (weak form)Feige✭✭✭0Theoretical Comp. Sci. » Complexity » Hardness of Approximationcwenner
P vs. PSPACEFolklore✭✭✭0Theoretical Comp. Sci. » Complexitycwenner
Inequality of the means✭✭✭0Geometrymdevos
Graphs with a forbidden induced tree are chi-boundedGyarfas✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Crossing numbers and coloringAlbertson✭✭✭0Graph Theory » Topological G.T. » Crossing numbersmdevos
Shuffle-Exchange Conjecture (graph-theoretic form)Beneš; Folklore; Stone✭✭✭0Graph TheoryVadim Lioubimov
Are different notions of the crossing number the same?Pach; Tóth✭✭✭0Graph Theory » Topological G.T. » Crossing numberscibulka
Which compact boundaryless 3-manifolds embed smoothly in the 4-sphere?Kirby✭✭✭0Topologyrybu
Is there an algorithm to determine if a triangulated 4-manifold is combinatorially equivalent to the 4-sphere?Novikov✭✭✭0Topologyrybu
Shuffle-Exchange ConjectureBeneš; Folklore; Stone✭✭✭0CombinatoricsVadim Lioubimov
Beneš ConjectureBeneš✭✭✭0CombinatoricsVadim Lioubimov
Beneš Conjecture (graph-theoretic form)Beneš✭✭✭0Graph TheoryVadim Lioubimov
Unsolvability of word problem for 2-knot complementsGordon✭✭✭0Topologyrybu
Strong 5-cycle double cover conjectureArthur; Hoffmann-Ostenhof✭✭✭1Graph Theory » Basic G.T. » Cyclesarthur
Polignac's Conjecturede Polignac✭✭✭0Number TheoryHugh Barker
Vertex Coloring of graph fractional powersIradmusa✭✭✭1Graph TheoryIradmusa
Euler-Mascheroni constant✭✭✭0Number Theory » Analytic N.T.Juggernaut
Durer's ConjectureDurer; Shephard✭✭✭1Geometry » Polytopesdmoskovich
Oriented trees in n-chromatic digraphsBurr✭✭✭0Graph Theory » Directed Graphsfhavet
Decomposing an even tournament in directed paths.Alspach; Mason; Pullman✭✭✭0Graph Theory » Directed Graphs » Tournamentsfhavet
Directed path of length twice the minimum outdegreeThomassé✭✭✭0Graph Theory » Directed Graphsfhavet
Ádám's ConjectureÁdám✭✭✭0Graph Theory » Directed Graphsfhavet
Splitting a digraph with minimum outdegree constraintsAlon✭✭✭0Graph Theory » Directed Graphsfhavet
Long directed cycles in diregular digraphsJackson✭✭✭0Graph Theory » Directed Graphsfhavet
Decomposing a connected graph into paths.Gallai✭✭✭0Graph Theory » Basic G.T. » Pathsfhavet
Acyclic list colouring of planar graphs.Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena✭✭✭0Graph Theory » Coloring » Vertex coloringfhavet
Hoàng-Reed ConjectureHoang; Reed✭✭✭0Graph Theory » Directed Graphsfhavet
The Bollobás-Eldridge-Catlin Conjecture on graph packing✭✭✭0Graph Theory » Extremal G.T.asp
Are almost all graphs determined by their spectrum?✭✭✭0Graph Theorymdevos
P vs. BPPFolklore✭✭✭0Theoretical Comp. Sci. » Complexity » DerandomizationCharles R Great...
Are all Fermat Numbers square-free?✭✭✭0Number Theory » Analytic N.T.kurtulmehtap
Are there only finite Fermat Primes?✭✭✭0Number Theory » Analytic N.T.kurtulmehtap
Erdős–Faber–Lovász conjectureErdos; Faber; Lovasz✭✭✭0Graph Theory » Coloring » Vertex coloringJon Noel
Roller Coaster permutationsAhmed; Snevily✭✭✭0CombinatoricsTanbir Ahmed
Are all Mersenne Numbers with prime exponent square-free?✭✭✭0Number Theory » Analytic N.T.kurtulmehtap
3-Decomposition ConjectureArthur; Hoffmann-Ostenhof✭✭✭0Graph Theoryarthur
Monochromatic reachability in arc-colored digraphsSands; Sauer; Woodrow✭✭✭0Graph Theory » Directed Graphsfhavet
Cycle Double Covers Containing Predefined 2-Regular SubgraphsArthur; Hoffmann-Ostenhof✭✭✭0Graph Theoryarthur
Monochromatic vertex colorings inherited from Perfect Matchings✭✭✭1Graph TheoryMario Krenn
Sidorenko's ConjectureSidorenko✭✭✭0Graph TheoryJon Noel
Multicolour Erdős--Hajnal ConjectureErdos; Hajnal✭✭✭0Graph Theory » Extremal G.T.Jon Noel
Several ways to apply a (multivalued) multiargument function to a family of filtersPorton✭✭✭0Topologyporton
3-Edge-Coloring ConjectureArthur; Hoffmann-Ostenhof✭✭✭1Graph Theoryarthur
KPZ Universality Conjecture✭✭✭0ProbabilityTomas Kojar
5-flow conjectureTutte✭✭✭✭0Graph Theory » Coloring » Nowhere-zero flowsmdevos
Cycle double cover conjectureSeymour; Szekeres✭✭✭✭0Graph Theory » Basic G.T. » Cyclesmdevos
The Berge-Fulkerson conjectureBerge; Fulkerson✭✭✭✭0Graph Theory » Basic G.T. » Matchingsmdevos
Diagonal Ramsey numbersErdos✭✭✭✭0Combinatorics » Ramsey Theorymdevos
The Erdos-Turan conjecture on additive basesErdos; Turan✭✭✭✭0Number Theory » Additive N.T.mdevos
Syndicate content