Open Problems


TitleAuthor(s)Imp.¹sort iconRec.²Area » Topic » SubtopicPosted by
Lucas Numbers Modulo m✭✭1Number TheoryMartin Erickson
Sum of prime and semiprime conjectureGeoffrey Marnell✭✭0Number Theoryprinceps
Giuga's Conjecture on PrimalityGiuseppe Giuga✭✭0Number Theoryprinceps
Alexa's Conjecture on PrimalityAlexa✭✭0Number Theoryprinceps
Minimal graphs with a prescribed number of spanning treesAzarija; Skrekovski✭✭1Graph Theoryazi
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
Convex uniform 5-polytopes✭✭1GeometryACW
Special MKimberling✭✭1Number Theoryvprusso
Chromatic number of random lifts of complete graphsAmit✭✭0Graph Theory » Probabilistic G.T.DOT
The Borodin-Kostochka ConjectureBorodin; Kostochka✭✭0Graph TheoryAndrew King
Finite entailment of Positive Horn logicMartin✭✭0Logic » Finite Model TheoryLucSegoufin
Vertex Cover Integrality GapAtserias✭✭0Logic » Finite Model Theorydberwanger
Inequality for square summable complex series Retkes✭✭1Analysistigris35711
Choice Number of k-Chromatic Graphs of Bounded OrderNoel✭✭1Graph Theory » Coloring » Vertex coloringJon Noel
Antidirected trees in digraphsAddario-Berry; Havet; Linhares Sales; Reed; Thomassé✭✭0Graph Theory » Directed Graphsfhavet
Stable set meeting all longest directed paths.Laborde; Payan; Xuong N.H.✭✭0Graph Theoryfhavet
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 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
Every 4-connected toroidal graph has a Hamilton cycleGrunbaum; Nash-Williams✭✭0Graph Theory » Topological G.T.fhavet
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
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
Syndicate content