Open Problems


TitleAuthor(s)Imp.¹Rec.²Area » Topic » Subtopicsort iconPosted by
A gold-grabbing gameRosenfeld✭✭0Graph Theory » Graph Algorithmsmdevos
PTAS for feedback arc set in tournamentsAilon; Alon✭✭0Graph Theory » Graph Algorithmsfhavet
The Erdös-Hajnal ConjectureErdos; Hajnal✭✭✭0Graph Theory » Extremal G.T.mdevos
What is the smallest number of disjoint spanning trees made a graph HamiltonianGoldengorin✭✭0Graph Theory » Extremal G.T.boris
Extremal problem on the number of tree endomorphismZhicong Lin✭✭1Graph Theory » Extremal G.T.shudeshijie
Complexity of the H-factor problem.Kühn; Osthus✭✭0Graph Theory » Extremal G.T.fhavet
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
The Bollobás-Eldridge-Catlin Conjecture on graph packing✭✭✭0Graph Theory » Extremal G.T.asp
Monochromatic reachability in edge-colored tournamentsErdos✭✭✭0Graph Theory » Directed Graphs » Tournamentsmdevos
Monochromatic reachability or rainbow trianglesSands; Sauer; Woodrow✭✭✭0Graph Theory » Directed Graphs » Tournamentsmdevos
Decomposing an even tournament in directed paths.Alspach; Mason; Pullman✭✭✭0Graph Theory » Directed Graphs » Tournamentsfhavet
Edge-disjoint Hamilton cycles in highly strongly connected tournaments.Thomassen✭✭0Graph Theory » Directed Graphs » Tournamentsfhavet
Partitionning a tournament into k-strongly connected subtournaments.Thomassen✭✭0Graph Theory » Directed Graphs » Tournamentsfhavet
Decomposing k-arc-strong tournament into k spanning strong digraphsBang-Jensen; Yeo✭✭0Graph Theory » Directed Graphs » Tournamentsfhavet
The Two Color ConjectureNeumann-Lara✭✭0Graph Theory » Directed Graphsmdevos
Woodall's ConjectureWoodall✭✭✭0Graph Theory » Directed Graphsmdevos
The Bermond-Thomassen ConjectureBermond; Thomassen✭✭0Graph Theory » Directed GraphsJS
Seymour's Second Neighbourhood ConjectureSeymour✭✭✭1Graph Theory » Directed Graphsnkorppi
Non-edges vs. feedback edge sets in digraphsChudnovsky; Seymour; Sullivan✭✭✭0Graph Theory » Directed Graphsmdevos
Oriented trees in n-chromatic digraphsBurr✭✭✭0Graph Theory » Directed Graphsfhavet
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
Splitting a digraph with minimum outdegree constraintsAlon✭✭✭0Graph Theory » Directed Graphsfhavet
Long directed cycles in diregular digraphsJackson✭✭✭0Graph Theory » Directed Graphsfhavet
Arc-disjoint out-branching and in-branchingThomassen✭✭0Graph Theory » Directed Graphsfhavet
Subdivision of a transitive tournament in digraphs with large outdegree. Mader✭✭0Graph Theory » Directed Graphsfhavet
Hamilton cycle in small d-diregular graphsJackson✭✭0Graph Theory » Directed Graphsfhavet
Hoàng-Reed ConjectureHoang; Reed✭✭✭0Graph Theory » Directed Graphsfhavet
Arc-disjoint directed cycles in regular directed graphsAlon; McDiarmid; Molloy✭✭0Graph Theory » Directed Graphsfhavet
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 cycles.Havet; Maia✭✭0Graph Theory » Directed Graphsfhavet
Strong colorabilityAharoni; Alon; Haxell✭✭✭0Graph Theory » Coloring » Vertex coloringberger
Reed's omega, delta, and chi conjectureReed✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Circular coloring triangle-free subcubic planar graphsGhebleh; Zhu✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Bounding the chromatic number of graphs with no odd holeGyarfas✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Oriented chromatic number of planar graphs✭✭0Graph Theory » Coloring » Vertex coloringRobert Samal
Coloring and immersionAbu-Khzam; Langston✭✭✭1Graph Theory » Coloring » Vertex coloringmdevos
Coloring the Odd Distance GraphRosenfeld✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Partial List ColoringAlbertson; Grossman; Haas✭✭✭0Graph Theory » Coloring » Vertex coloringIradmusa
Partial List ColoringIradmusa✭✭✭0Graph Theory » Coloring » Vertex coloringIradmusa
Hedetniemi's ConjectureHedetniemi✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Counting 3-colorings of the hex latticeThomassen✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Circular colouring the orthogonality graphDeVos; Ghebleh; Goddyn; Mohar; Naserasr✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Double-critical graph conjectureErdos; Lovasz✭✭0Graph Theory » Coloring » Vertex coloringDFR
Bounding the chromatic number of triangle-free graphs with fixed maximum degreeKostochka; Reed✭✭0Graph Theory » Coloring » Vertex coloringAndrew King
Graphs with a forbidden induced tree are chi-boundedGyarfas✭✭✭0Graph Theory » Coloring » Vertex coloringmdevos
Syndicate content