Home

Open Problems


TitleAuthor(s)sort iconImp.¹Rec.²Area » Topic » SubtopicPosted by
What is the largest graph of positive curvature?DeVos; Mohar✭1Graph Theory » Topological G.T. » Planar graphsmdevos
Drawing disconnected graphs on surfacesDeVos; Mohar; Samal✭✭0Graph Theory » Topological G.T. » Crossing numbersmdevos
Average diameter of a bounded cell of a simple arrangementDeza; Terlaky; Zinchenko✭✭0Geometrydeza
Continous analogue of Hirsch conjectureDeza; Terlaky; Zinchenko✭✭0Geometry » Polytopesdeza
Characterizing (aleph_0,aleph_1)-graphsDiestel; Leader✭✭✭0Graph Theory » Infinite Graphsmdevos
Ding's tau_r vs. tau conjectureDing✭✭✭0Combinatorics » Optimizationmdevos
Dirac's ConjectureDirac✭✭0GeometryDavid Wood
Durer's ConjectureDurer; Shephard✭✭✭1Geometry » Polytopesdmoskovich
Star chromatic index of cubic graphsDvorak; Mohar; Samal✭✭0Graph TheoryRobert Samal
Star chromatic index of complete graphsDvorak; Mohar; Samal✭✭1Graph TheoryRobert Samal
Something like Picard for 1-formsElsner✭✭0AnalysisMathOMan
Fat 4-polytopesEppstein; Kuperberg; Ziegler✭✭✭0Geometry » Polytopesmdevos
Diagonal Ramsey numbersErdos✭✭✭✭0Combinatorics » Ramsey Theorymdevos
Sets with distinct subset sumsErdos✭✭✭0Number Theory » Combinatorial N.T.mdevos
Turán Problem for $10$-Cycles in the HypercubeErdos✭✭0CombinatoricsJon Noel
Erdős–Faber–Lovász conjectureErdos; Faber; Lovasz✭✭✭0Graph Theory » Coloring » Vertex coloringJon Noel
Odd-cycle transversal in triangle-free graphsErdos; Faudree; Pach; Spencer✭✭0Graph Theory » Extremal G.T.fhavet
The Crossing Number of the HypercubeErdos; Guy✭✭0Graph Theory » Topological G.T. » Crossing numbersRobert Samal
The Erdös-Hajnal ConjectureErdos; Hajnal✭✭✭0Graph Theory » Extremal G.T.mdevos
Unions of triangle free graphsErdos; Hajnal✭✭✭0Graph Theory » Infinite Graphsmdevos
Multicolour Erdős--Hajnal ConjectureErdos; Hajnal✭✭✭0Graph Theory » Extremal G.T.Jon Noel
Double-critical graph conjectureErdos; Lovasz✭✭0Graph Theory » Coloring » Vertex coloringDFR
Strong edge colouring conjectureErdos; Nesetril✭✭0Graph Theory » Coloring » Edge coloringfhavet
Odd incongruent covering systemsErdos; Selfridge✭✭✭0Number Theory » Combinatorial N.T.Robert Samal
Covering systems with big moduliErdos; Selfridge✭✭0Number Theory » Combinatorial N.T.Robert Samal
Turán number of a finite family.Erdos; Simonovits✭✭0Graph Theoryfhavet
Erdős–Straus conjectureErdos; Straus✭✭1Number TheoryACW
Erdös-Szekeres conjectureErdos; Szekeres✭✭✭0Geometrymdevos
The Erdos-Turan conjecture on additive basesErdos; Turan✭✭✭✭0Number Theory » Additive N.T.mdevos
Sequence defined on multisetsErickson✭✭1CombinatoricsMartin Erickson
Square achievement game on an n x n gridErickson✭✭1CombinatoricsMartin Erickson
Exact colorings of graphsErickson✭✭0Graph TheoryMartin Erickson
Transversal achievement game on a square gridErickson✭✭1CombinatoricsMartin Erickson
A sextic counterexample to Euler's sum of powers conjectureEuler✭✭1Number Theory » Computational N.T.maxal
Chromatic number of associahedronFabila-Monroy; Flores-Penaloza; Huemer; Hurtado; Urrutia; Wood✭✭1GeometryDavid Wood
Refuting random 3SAT-instances on $O(n)$ clauses (weak form)Feige✭✭✭0Theoretical Comp. Sci. » Complexity » Hardness of Approximationcwenner
Sums of independent random variables with unbounded varianceFeige✭✭0Theoretical Comp. Sci.cwenner
3-Colourability of Arrangements of Great CirclesFelsner; Hurtado; Noy; Streinu✭✭1Graph Theory » Topological G.T. » ColoringDavid Wood
Acyclic edge-colouringFiamcik✭✭0Graph Theory » Coloring » Edge coloringmdevos
4-connected graphs are not uniquely hamiltonianFleischner✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
P vs. PSPACEFolklore✭✭✭0Theoretical Comp. Sci. » Complexitycwenner
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

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

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

Syndicate content