Home

Open Problems


TitleAuthor(s)Imp.¹Rec.²Area » Topic » SubtopicPosted bysort icon
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
Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournamentYuster✭✭0Graph Theoryfhavet
Odd cycles and low oddness✭✭0Graph TheoryGagik
Three-chromatic (0,2)-graphsPayan✭✭0Graph Theory » ColoringGordon Royle
Equality in a matroidal circumference boundOxley; Royle✭✭0Combinatorics » Matroid TheoryGordon Royle
Twin Primes and Polignac's Conjecture✭✭✭0Number TheoryHugh Barker
Partial List ColoringAlbertson; Grossman; Haas✭✭✭0Graph Theory » Coloring » Vertex coloringIradmusa
Partial List ColoringIradmusa✭✭✭0Graph Theory » Coloring » Vertex coloringIradmusa
Total Colouring ConjectureBehzad✭✭✭0Graph Theory » ColoringIradmusa
Vertex Coloring of graph fractional powersIradmusa✭✭✭1Graph TheoryIradmusa
Closing Lemma for Diffeomorphism (Dynamical Systems)Charles Pugh✭✭✭✭0TopologyJailton Viana
Jacob Palis Conjecture(Finitude of Attractors)(Dynamical Systems)✭✭✭✭0TopologyJailton Viana
Approximation Ratio for Maximum Edge Disjoint Paths problemBentz✭✭0Graph Theoryjcmeyer
Approximation ratio for k-outerplanar graphsBentz✭✭0Graph Theoryjcmeyer
Finding k-edge-outerplanar graph embeddingsBentz✭✭0Graph Theoryjcmeyer
Rank vs. GenusJohnson✭✭✭0TopologyJesse Johnson
Algorithm for graph homomorphismsFomin; Heggernes; Kratsch✭✭0Graph Theory » Coloring » Homomorphismsjfoniok
Matchings extend to Hamiltonian cycles in hypercubesRuskey; Savage✭✭1Graph Theory » Basic G.T. » MatchingsJirka
Mixing Circular ColouringsBrewster; Noel✭1Graph Theory » Coloring » Vertex coloringjnoel12
Choice Number of k-Chromatic Graphs of Bounded OrderNoel✭✭1Graph Theory » Coloring » Vertex coloringjnoel12
Choice number of complete multipartite graphs with parts of size 4✭1Graph Theory » Coloring » Vertex coloringjnoel12
On-Line Ohba's ConjectureHuang; Wong; Zhu✭✭1Graph Theory » Coloring » Vertex coloringjnoel12
Bounding the on-line choice number in terms of the choice numberZhu✭✭1Graph Theory » Coloring » Vertex coloringjnoel12
The Bermond-Thomassen ConjectureBermond; Thomassen✭✭0Graph Theory » Directed GraphsJS
Euler-Mascheroni constant✭✭✭0Number Theory » Analytic N.T.Juggernaut
Twin prime conjecture✭✭✭✭0Number Theorykaushiks.nitt
Graceful Tree Conjecture✭✭✭0Graph Theory » Coloring » Labelingkintali
Linear-size circuits for stable $0,1 < 2$ sorting?Regan✭✭1Theoretical Comp. Sci. » ComplexityKWRegan
Finite entailment of Positive Horn logicMartin✭✭0Logic » Finite Model TheoryLucSegoufin
Length of surreal productGonshor✭1CombinatoricsLukáš Lánský
$C^r$ Stability ConjecturePalis; Smale✭✭✭✭0Analysism n
Universal Steiner triple systemsGrannell; Griggs; Knor; Skoviera✭✭0Graph Theory » Coloring » Edge coloringmacajova
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

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

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

Syndicate content