Home

Open Problems


TitleAuthor(s)Imp.¹Rec.²Area » Topic » SubtopicPosted bysort icon
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
Average diameter of a bounded cell of a simple arrangementDeza; Terlaky; Zinchenko✭✭0Geometrydeza
Continous analogue of Hirsch conjectureDeza; Terlaky; Zinchenko✭✭0Geometry » Polytopesdeza
Double-critical graph conjectureErdos; Lovasz✭✭0Graph Theory » Coloring » Vertex coloringDFR
Exponential Algorithms for KnapsackLipton✭✭1Theoretical Comp. Sci. » Algorithmsdick lipton
¿Are critical k-forests tight?Strausz✭✭0Graph Theory » HypergraphsDino
Subgroup formed by elements of order dividing nFrobenius✭✭0Group Theorydlh12
Inscribed Square ProblemToeplitz✭✭0Topologydlh12
Burnside problemBurnside✭✭✭✭0Group Theorydlh12
Durer's ConjectureDurer; Shephard✭✭✭1Geometry » Polytopesdmoskovich
The 3n+1 conjectureCollatz✭✭✭0Number Theory » Combinatorial N.T.dododododo
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 Riemann HypothesisRiemann✭✭✭✭0Number Theory » Analytic N.T.eric
Birch & Swinnerton-Dyer conjecture✭✭✭✭0Number Theoryeyoong
Distribution and upper bound of mimic numbersBhattacharyya✭✭1Number Theory » Analytic N.T.facility_cttb@i...
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
Antidirected trees in digraphsAddario-Berry; Havet; Linhares Sales; Reed; Thomassé✭✭0Graph Theory » Directed Graphsfhavet
Directed path of length twice the minimum outdegreeThomassé✭✭✭0Graph Theory » Directed Graphsfhavet
Caccetta-Häggkvist ConjectureCaccetta; Häggkvist✭✭✭✭0Graph Theory » Directed Graphsfhavet
Ádám's ConjectureÁdám✭✭✭0Graph Theory » Directed Graphsfhavet
Stable set meeting all longest directed paths.Laborde; Payan; Xuong N.H.✭✭0Graph Theoryfhavet
Splitting a digraph with minimum outdegree constraintsAlon✭✭✭0Graph Theory » Directed Graphsfhavet
Long directed cycles in diregular digraphsJackson✭✭✭0Graph Theory » Directed Graphsfhavet
Strong edge colouring conjectureErdos; Nesetril✭✭0Graph Theory » Coloring » Edge coloringfhavet
Arc-disjoint out-branching and in-branchingThomassen✭✭0Graph Theory » Directed Graphsfhavet
Arc-disjoint strongly connected spanning subdigraphsBang-Jensen; Yeo✭✭0Graph Theoryfhavet
Coloring the union of degenerate graphsTarsi✭✭0Graph Theory » Coloringfhavet
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
Decomposing an eulerian graph into cycles.Hajós✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour.Sabidussi✭✭0Graph Theory » Basic G.T. » Cyclesfhavet
Partition of a cubic 3-connected graphs into paths of length 2.Kelmans✭✭0Graph Theory » Basic G.T. » Pathsfhavet
Lovász Path Removal ConjectureLovasz✭✭0Graph Theoryfhavet
Large induced forest in a planar graph.Abertson; Berman✭✭0Graph Theory » Topological G.T.fhavet
Subdivision of a transitive tournament in digraphs with large outdegree. Mader✭✭0Graph Theory » Directed Graphsfhavet
Turán number of a finite family.Erdos; Simonovits✭✭0Graph Theoryfhavet
Subgraph of large average degree and large girth.Thomassen✭✭0Graph Theory » Basic G.T.fhavet
Complexity of the H-factor problem.Kühn; Osthus✭✭0Graph Theory » Extremal G.T.fhavet
Simultaneous partition of hypergraphsKühn; Osthus✭✭0Graph Theory » Hypergraphsfhavet
Odd-cycle transversal in triangle-free graphsErdos; Faudree; Pach; Spencer✭✭0Graph Theory » Extremal G.T.fhavet
Triangle-packing vs triangle edge-transversal.Tuza✭✭0Graph Theory » Extremal G.T.fhavet
Earth-Moon ProblemRingel✭✭1Graph Theory » Coloring » Vertex coloringfhavet
Acyclic list colouring of planar graphs.Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena✭✭✭0Graph Theory » Coloring » Vertex coloringfhavet

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

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

Syndicate content