Home

Open Problems


TitleAuthor(s)Imp.¹Rec.²Area » Topic » SubtopicPosted bysort icon
Switching reconstruction conjectureStanley✭✭0Graph Theoryfhavet
Switching reconstruction of digraphsBondy; Mercier✭✭0Graph Theoryfhavet
Hamilton cycle in small d-diregular graphsJackson✭✭0Graph Theory » Directed Graphsfhavet
Edge-disjoint Hamilton cycles in highly strongly connected tournaments.Thomassen✭✭0Graph Theory » Directed Graphs » Tournamentsfhavet
Hoàng-Reed ConjectureHoang; Reed✭✭✭0Graph Theory » Directed Graphsfhavet
Every prism over a 3-connected planar graph is hamiltonian.Kaiser; Král; Rosenfeld; Ryjácek; Voss✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
4-connected graphs are not uniquely hamiltonianFleischner✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
Turán's problem for hypergraphsTuran✭✭0Graph Theory » Hypergraphsfhavet
Hamilton decomposition of prisms over 3-connected cubic planar graphsAlspach; Rosenfeld✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
List chromatic number and maximum degree of bipartite graphsAlon✭✭0Graph Theory » Coloring » Vertex coloringfhavet
Colouring the square of a planar graphWegner✭✭0Graph Theory » Coloring » Vertex coloringfhavet
Weighted colouring of hexagonal graphs.McDiarmid; Reed✭✭0Graph Theory » Coloring » Vertex coloringfhavet
Partitionning a tournament into k-strongly connected subtournaments.Thomassen✭✭0Graph Theory » Directed Graphs » Tournamentsfhavet
PTAS for feedback arc set in tournamentsAilon; Alon✭✭0Graph Theory » Graph Algorithmsfhavet
Decomposing k-arc-strong tournament into k spanning strong digraphsBang-Jensen; Yeo✭✭0Graph Theory » Directed Graphs » Tournamentsfhavet
Arc-disjoint directed cycles in regular directed graphsAlon; McDiarmid; Molloy✭✭0Graph Theory » Directed Graphsfhavet
Distribution and upper bound of mimic numbersBhattacharyya✭✭1Number Theory » Analytic N.T.facility_cttb@i...
Birch & Swinnerton-Dyer conjecture✭✭✭✭0Number Theoryeyoong
The Riemann HypothesisRiemann✭✭✭✭0Number Theory » Analytic N.T.eric
Good Edge LabelingsAraújo; Cohen; Giroire; Havet✭✭0Graph Theory » Coloring » LabelingDOT
Extension complexity of (convex) polygons✭✭0Geometry » PolytopesDOT
Chromatic number of random lifts of complete graphsAmit✭✭0Graph Theory » Probabilistic G.T.DOT
The 3n+1 conjectureCollatz✭✭✭0Number Theory » Combinatorial N.T.dododododo
Durer's ConjectureDurer; Shephard✭✭✭1Geometry » Polytopesdmoskovich
Subgroup formed by elements of order dividing nFrobenius✭✭0Group Theorydlh12
Inscribed Square ProblemToeplitz✭✭0Topologydlh12
Burnside problemBurnside✭✭✭✭0Group Theorydlh12
¿Are critical k-forests tight?Strausz✭✭0Graph Theory » HypergraphsDino
Exponential Algorithms for KnapsackLipton✭✭1Theoretical Comp. Sci. » Algorithmsdick lipton
Double-critical graph conjectureErdos; Lovasz✭✭0Graph Theory » Coloring » Vertex coloringDFR
Average diameter of a bounded cell of a simple arrangementDeza; Terlaky; Zinchenko✭✭0Geometrydeza
Continous analogue of Hirsch conjectureDeza; Terlaky; Zinchenko✭✭0Geometry » Polytopesdeza
Fixed-point logic with countingBlass✭✭0Logic » Finite Model Theorydberwanger
Order-invariant queriesSegoufin✭✭0Logic » Finite Model Theorydberwanger
Monadic second-order logic with cardinality predicatesCourcelle✭✭0Logic » Finite Model Theorydberwanger
Blatter-Specker Theorem for ternary relationsMakowsky✭✭0Logic » Finite Model Theorydberwanger
MSO alternation hierarchy over picturesGrandjean✭✭0Logic » Finite Model Theorydberwanger
Vertex Cover Integrality GapAtserias✭✭0Logic » Finite Model Theorydberwanger
Dividing up the unrestricted partitionsDavid S.; Newman✭✭0CombinatoricsDavidSNewman
Perfect 2-error-correcting codes over arbitrary finite alphabets.✭✭0Combinatorics » Codesdavidcullen
Big Line or Big Clique in Planar Point SetsKara; Por; Wood✭✭1GeometryDavid Wood
Book Thickness of SubdivisionsBlankenship; Oporowski✭✭1Graph TheoryDavid Wood
3-Colourability of Arrangements of Great CirclesFelsner; Hurtado; Noy; Streinu✭✭1Graph Theory » Topological G.T. » ColoringDavid Wood
Number of Cliques in Minor-Closed ClassesWood✭✭0Graph TheoryDavid Wood
Edge-Colouring Geometric Complete GraphsHurtado✭✭1GeometryDavid Wood
Partition of Complete Geometric Graph into Plane Trees✭✭0GeometryDavid Wood
Point sets with no empty pentagonWood✭1GeometryDavid Wood
Forcing a $K_6$-minorBarát ; Joret; Wood✭✭0Graph Theory » Basic G.T. » MinorsDavid 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

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

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

Syndicate content