Open Problems


TitleAuthor(s)Imp.¹Rec.²Area » Topic » SubtopicPosted bysort icon
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
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
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
Cyclic spanning subdigraph with small cyclomatic numberBondy✭✭0Graph Theory » Directed Graphsfhavet
Large acyclic induced subdigraph in a planar oriented graph.Harutyunyan✭✭0Graph Theory » Directed Graphsfhavet
Erdős-Posa property for long directed cyclesHavet; Maia✭✭0Graph Theory » Directed Graphsfhavet
Monochromatic reachability in arc-colored digraphsSands; Sauer; Woodrow✭✭✭0Graph Theory » Directed Graphsfhavet
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
Polignac's Conjecturede Polignac✭✭✭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
Chromatic number of $\frac{3}{3}$-power of graph✭✭0Graph 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
Syndicate content