Graph-theory open problems

Graph Theory

subject tag · 227 problems

Title Source Status Imp. Posted
Caccetta-Häggkvist Conjecture opg open ★★★★ 2013-02-28
5-flow conjecture opg partial ★★★★ 2007-03-07
Cycle double cover conjecture opg partial ★★★★ 2007-03-07
Reconstruction conjecture opg partial ★★★★ 2007-10-18
The Berge-Fulkerson conjecture opg partial ★★★★ 2007-03-07
3-Edge-Coloring Conjecture opg partial ★★★ 2020-04-28
Monochromatic vertex colorings inherited from Perfect Matchings opg partial ★★★ 2019-03-04
Multicolour Erdős--Hajnal Conjecture opg partial ★★★ 2019-10-10
Sidorenko's Conjecture opg partial ★★★ 2019-10-10
3-Decomposition Conjecture opg partial ★★★ 2017-01-24
Cycle Double Covers Containing Predefined 2-Regular Subgraphs opg partial ★★★ 2017-06-21
Monochromatic reachability in arc-colored digraphs opg open ★★★ 2017-04-04
Acyclic list colouring of planar graphs. opg partial ★★★ 2013-03-07
Are almost all graphs determined by their spectrum? opg partial ★★★ 2013-03-26
Decomposing a connected graph into paths. opg partial ★★★ 2013-03-04
Decomposing an even tournament in directed paths. opg partial ★★★ 2013-02-26
Directed path of length twice the minimum outdegree opg partial ★★★ 2013-02-28
Erdős–Faber–Lovász conjecture opg partial ★★★ 2013-08-22
Hoàng-Reed Conjecture opg open ★★★ 2013-03-11
Long directed cycles in diregular digraphs opg open ★★★ 2013-03-01
Oriented trees in n-chromatic digraphs opg partial ★★★ 2013-02-25
Splitting a digraph with minimum outdegree constraints opg partial ★★★ 2013-03-01
The Bollobás-Eldridge-Catlin Conjecture on graph packing opg partial ★★★ 2013-03-23
Ádám's Conjecture opg disproved ★★★ 2013-03-01
Vertex Coloring of graph fractional powers opg disproved ★★★ 2011-04-23
Beneš Conjecture (graph-theoretic form) opg open ★★★ 2010-04-17
Strong 5-cycle double cover conjecture opg partial ★★★ 2010-08-03
Are different notions of the crossing number the same? opg partial ★★★ 2009-11-03
Crossing numbers and coloring opg partial ★★★ 2009-09-04
Graphs with a forbidden induced tree are chi-bounded opg partial ★★★ 2009-05-16
Shannon capacity of the seven-cycle opg partial ★★★ 2009-02-19
Shuffle-Exchange Conjecture (graph-theoretic form) opg open ★★★ 2009-10-30
Characterizing (aleph_0,aleph_1)-graphs opg partial ★★★ 2008-06-26
Cores of strongly regular graphs opg solved ★★★ 2008-06-16
Degenerate colorings of planar graphs opg partial ★★★ 2008-05-21
Edge list coloring conjecture opg open ★★★ 2008-09-25
Edge Reconstruction Conjecture opg open ★★★ 2008-05-23
Goldberg's conjecture opg solved ★★★ 2008-10-04
Hamiltonicity of Cayley graphs opg partial ★★★ 2008-09-25
Hedetniemi's Conjecture opg disproved ★★★ 2008-05-25
Monochromatic reachability or rainbow triangles opg partial ★★★ 2008-07-15
Nearly spanning regular subgraphs opg open ★★★ 2008-05-22
Non-edges vs. feedback edge sets in digraphs opg partial ★★★ 2008-07-08
Partial List Coloring opg partial ★★★ 2008-05-05
Partial List Coloring opg partial ★★★ 2008-05-12
Seagull problem opg partial ★★★ 2008-01-06
Seymour's r-graph conjecture opg solved ★★★ 2008-10-03
Total Colouring Conjecture opg partial ★★★ 2008-06-04
(m,n)-cycle covers opg partial ★★★ 2007-03-07
3-flow conjecture opg partial ★★★ 2007-03-07
4-flow conjecture opg partial ★★★ 2007-03-07
57-regular Moore graph? opg open ★★★ 2007-03-18
Barnette's Conjecture opg partial ★★★ 2007-06-12
Bouchet's 6-flow conjecture opg partial ★★★ 2007-03-07
Chords of longest cycles opg partial ★★★ 2007-11-12
Coloring and immersion opg partial ★★★ 2007-09-04
Coloring the Odd Distance Graph opg solved ★★★ 2007-10-03
Consecutive non-orientable embedding obstructions opg open ★★★ 2007-03-27
Decomposing eulerian graphs opg partial ★★★ 2007-03-07
Faithful cycle covers opg open ★★★ 2007-03-07
Graceful Tree Conjecture opg partial ★★★ 2007-07-13
Grunbaum's Conjecture opg disproved ★★★ 2007-04-04
Hamiltonian cycles in line graphs opg partial ★★★ 2007-07-24
Hamiltonian paths and cycles in vertex transitive graphs opg partial ★★★ 2007-03-18
Highly connected graphs with no K_n minor opg partial ★★★ 2007-03-10
Jaeger's modular orientation conjecture opg disproved ★★★ 2007-03-07
Jorgensen's Conjecture opg partial ★★★ 2007-03-10
Linial-Berge path partition duality opg partial ★★★ 2007-03-27
Mapping planar graphs to odd cycles opg partial ★★★ 2007-06-24
Pebbling a cartesian product opg partial ★★★ 2007-09-24
Pentagon problem opg open ★★★ 2007-03-24
Petersen coloring conjecture opg partial ★★★ 2007-03-07
r-regular graphs are not uniquely hamiltonian. opg partial ★★★ 2007-07-24
Ramsey properties of Cayley graphs opg partial ★★★ 2007-06-10
Reed's omega, delta, and chi conjecture opg partial ★★★ 2007-05-22
Ryser's conjecture opg partial ★★★ 2007-03-19
Seymour's Second Neighbourhood Conjecture opg partial ★★★ 2007-10-09
Seymour's self-minor conjecture opg partial ★★★ 2007-05-22
Strong colorability opg partial ★★★ 2007-03-27
Strong matchings and covers opg disproved ★★★ 2007-10-23
The circular embedding conjecture opg partial ★★★ 2007-03-07
The Crossing Number of the Complete Bipartite Graph opg partial ★★★ 2007-05-11
The Crossing Number of the Complete Graph opg partial ★★★ 2007-05-11
The Erdös-Hajnal Conjecture opg partial ★★★ 2007-03-18
Triangle free strongly regular graphs opg open ★★★ 2007-05-28
Unfriendly partitions opg partial ★★★ 2007-10-22
Unions of triangle free graphs opg open ★★★ 2007-06-04
Universal highly arc transitive digraphs opg solved ★★★ 2007-10-21
Universal point sets for planar graphs opg partial ★★★ 2007-05-22
Woodall's Conjecture opg partial ★★★ 2007-04-05
Chromatic number of $\frac{3}{3}$-power of graph opg partial ★★ 2023-04-20
Circular flow number of regular class 1 graphs opg disproved ★★ 2015-08-05
Circular flow numbers of $r$-graphs opg disproved ★★ 2015-08-06
Cycles in Graphs of Large Chromatic Number opg partial ★★ 2015-09-20
Chromatic Number of Common Graphs opg solved ★★ 2014-08-15
Forcing a 2-regular minor opg solved ★★ 2014-03-16
Fractional Hadwiger opg open ★★ 2014-03-16
List Colourings of Complete Multipartite Graphs with 2 Big Parts opg partial ★★ 2014-04-12
List Hadwiger Conjecture opg partial ★★ 2014-07-07
2-colouring a graph without a monochromatic maximum clique opg partial ★★ 2013-08-25
4-connected graphs are not uniquely hamiltonian opg open ★★ 2013-03-11
Almost all non-Hamiltonian 3-regular graphs are 1-connected opg open ★★ 2013-08-23
Antidirected trees in digraphs opg partial ★★ 2013-02-26
Arc-disjoint directed cycles in regular directed graphs opg open ★★ 2013-05-17
Arc-disjoint out-branching and in-branching opg partial ★★ 2013-03-02
Arc-disjoint strongly connected spanning subdigraphs opg partial ★★ 2013-03-02
Bounding the on-line choice number in terms of the choice number opg solved ★★ 2013-04-11
Choice Number of k-Chromatic Graphs of Bounded Order opg partial ★★ 2013-02-02
Choosability of Graph Powers opg open ★★ 2013-07-13
Coloring the union of degenerate graphs opg open ★★ 2013-03-03
Colouring the square of a planar graph opg partial ★★ 2013-03-13
Complexity of the H-factor problem. opg partial ★★ 2013-03-05
Cyclic spanning subdigraph with small cyclomatic number opg open ★★ 2013-06-02
Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour. opg open ★★ 2013-03-04
Decomposing an eulerian graph into cycles. opg partial ★★ 2013-03-04
Decomposing k-arc-strong tournament into k spanning strong digraphs opg partial ★★ 2013-03-15
Do any three longest paths in a connected graph have a vertex in common? opg partial ★★ 2013-03-03
Earth-Moon Problem opg partial ★★ 2013-03-06
Edge-disjoint Hamilton cycles in highly strongly connected tournaments. opg solved ★★ 2013-03-08
Erdős-Posa property for long directed cycles opg solved ★★ 2013-06-25
Every 4-connected toroidal graph has a Hamilton cycle opg open ★★ 2013-03-07
Every prism over a 3-connected planar graph is hamiltonian. opg disproved ★★ 2013-03-11
Hamilton cycle in small d-diregular graphs opg partial ★★ 2013-03-08
Hamilton decomposition of prisms over 3-connected cubic planar graphs opg partial ★★ 2013-03-12
Imbalance conjecture opg partial ★★ 2013-09-24
Kriesell's Conjecture opg partial ★★ 2013-08-25
Large acyclic induced subdigraph in a planar oriented graph. opg partial ★★ 2013-06-25
Large induced forest in a planar graph. opg partial ★★ 2013-03-04
List chromatic number and maximum degree of bipartite graphs opg partial ★★ 2013-03-12
List Total Colouring Conjecture opg open ★★ 2013-08-29
Lovász Path Removal Conjecture opg open ★★ 2013-03-04
Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament opg open ★★ 2013-05-21
Odd-cycle transversal in triangle-free graphs opg partial ★★ 2013-03-06
Partition of a cubic 3-connected graphs into paths of length 2. opg open ★★ 2013-03-04
Partitionning a tournament into k-strongly connected subtournaments. opg solved ★★ 2013-03-15
PTAS for feedback arc set in tournaments opg solved ★★ 2013-03-15
Signing a graph to have small magnitude eigenvalues opg partial ★★ 2013-03-24
Simultaneous partition of hypergraphs opg open ★★ 2013-03-06
Stable set meeting all longest directed paths. opg open ★★ 2013-03-01
Strong edge colouring conjecture opg partial ★★ 2013-03-01
Subdivision of a transitive tournament in digraphs with large outdegree. opg partial ★★ 2013-03-04
Subgraph of large average degree and large girth. opg partial ★★ 2013-03-05
Switching reconstruction conjecture opg open ★★ 2013-03-07
Switching reconstruction of digraphs opg partial ★★ 2013-03-07
Triangle-packing vs triangle edge-transversal. opg partial ★★ 2013-03-06
Turán number of a finite family. opg partial ★★ 2013-03-05
Turán's problem for hypergraphs opg open ★★ 2013-03-12
Weighted colouring of hexagonal graphs. opg partial ★★ 2013-03-13
Chromatic number of random lifts of complete graphs opg partial ★★ 2012-09-03
Forcing a $K_6$-minor opg partial ★★ 2012-01-16
Minimal graphs with a prescribed number of spanning trees opg partial ★★ 2012-04-22
The Borodin-Kostochka Conjecture opg partial ★★ 2012-09-10
Extremal problem on the number of tree endomorphism opg solved ★★ 2011-03-01
Good Edge Labelings opg partial ★★ 2011-06-30
Matching cut and girth opg partial ★★ 2011-11-30
Algorithm for graph homomorphisms opg partial ★★ 2010-07-08
Approximation ratio for k-outerplanar graphs opg partial ★★ 2010-04-18
Approximation Ratio for Maximum Edge Disjoint Paths problem opg partial ★★ 2010-04-18
Exact colorings of graphs opg partial ★★ 2010-06-29
Finding k-edge-outerplanar graph embeddings opg open ★★ 2010-04-18
Odd cycles and low oddness opg open ★★ 2010-01-15
Star chromatic index of complete graphs opg open ★★ 2010-11-16
Star chromatic index of cubic graphs opg partial ★★ 2010-11-16
3-Colourability of Arrangements of Great Circles opg partial ★★ 2009-01-19
A gold-grabbing game opg partial ★★ 2009-10-02
Are vertex minor closed classes chi-bounded? opg solved ★★ 2009-05-16
Asymptotic Distribution of Form of Polyhedra opg open ★★ 2009-05-09
Book Thickness of Subdivisions opg disproved ★★ 2009-01-19
Bounding the chromatic number of triangle-free graphs with fixed maximum degree opg open ★★ 2009-04-17
Does the chromatic symmetric function distinguish between trees? opg partial ★★ 2009-02-25
Domination in cubic graphs opg open ★★ 2009-08-19
Domination in plane triangulations opg partial ★★ 2009-05-04
Double-critical graph conjecture opg partial ★★ 2009-01-18
Friendly partitions opg partial ★★ 2009-11-08
Number of Cliques in Minor-Closed Classes opg solved ★★ 2009-10-12
4-regular 4-chromatic graphs of high girth opg open ★★ 2008-06-18
Circular colouring the orthogonality graph opg open ★★ 2008-09-23
Coloring random subgraphs opg partial ★★ 2008-06-18
Complete bipartite subgraphs of perfect graphs opg open ★★ 2008-06-17
Counting 3-colorings of the hex lattice opg open ★★ 2008-07-05
Crossing sequences opg partial ★★ 2008-07-30
Frankl's union-closed sets conjecture opg partial ★★ 2008-09-25
Negative association in uniform forests opg partial ★★ 2008-06-30
Random stable roommates opg partial ★★ 2008-02-26
5-local-tensions opg open ★★ 2007-06-22
A generalization of Vizing's Theorem? opg open ★★ 2007-04-11
A homomorphism problem for flows opg partial ★★ 2007-03-07
Acyclic edge-colouring opg partial ★★ 2007-03-07
Antichains in the cycle continuous order opg solved ★★ 2007-05-12
Circular coloring triangle-free subcubic planar graphs opg open ★★ 2007-06-20
Cores of Cayley graphs opg partial ★★ 2007-03-06
Drawing disconnected graphs on surfaces opg partial ★★ 2007-05-12
Geodesic cycles and Tutte's Theorem opg open ★★ 2007-08-04
Graham's conjecture on tree reconstruction opg partial ★★ 2007-03-18
Half-integral flow polynomial values opg open ★★ 2007-05-31
Hamiltonian cycles in line graphs of infinite graphs opg partial ★★ 2007-07-24
Hamiltonian cycles in powers of infinite graphs opg open ★★ 2007-07-24
Highly arc transitive two ended digraphs opg disproved ★★ 2007-10-29
Infinite uniquely hamiltonian graphs opg partial ★★ 2007-07-24
Jones' conjecture opg partial ★★ 2007-10-09
Laplacian Degrees of a Graph opg solved ★★ 2007-06-22
Linear Hypergraphs with Dimension 3 opg open ★★ 2007-09-26
List colorings of edge-critical graphs opg open ★★ 2007-06-12
Matchings extend to Hamiltonian cycles in hypercubes opg partial ★★ 2007-09-28
Oriented chromatic number of planar graphs opg partial ★★ 2007-08-04
Packing T-joins opg partial ★★ 2007-03-07
Partitioning edge-connectivity opg open ★★ 2007-03-07
Real roots of the flow polynomial opg disproved ★★ 2007-03-07
The Bermond-Thomassen Conjecture opg partial ★★ 2007-10-01
The Crossing Number of the Hypercube opg partial ★★ 2007-05-11
The intersection of two perfect matchings opg partial ★★ 2007-08-30
The three 4-flows conjecture opg open ★★ 2007-03-07
The Two Color Conjecture opg partial ★★ 2007-03-26
Three-chromatic (0,2)-graphs opg open ★★ 2007-09-07
Unit vector flows opg partial ★★ 2007-03-07
Universal Steiner triple systems opg partial ★★ 2007-10-05
Weak pentagon problem opg partial ★★ 2007-07-13
What is the smallest number of disjoint spanning trees made a graph Hamiltonian opg unclear ★★ 2007-09-10
¿Are critical k-forests tight? opg disproved ★★ 2007-09-01
Weak saturation of the cube in the clique opg open ★ 2016-04-06
Melnikov's valency-variety problem opg open ★ 2013-03-03
Circular choosability of planar graphs opg open ★ 2012-08-23
Mixing Circular Colourings opg partial ★ 2012-09-22
Covering powers of cycles with equivalence subgraphs opg open ★ 2011-07-07
Obstacle number of planar graphs opg partial ★ 2011-11-23
End-Devouring Rays opg solved ★ 2008-02-03
What is the largest graph of positive curvature? opg solved ★ 2007-03-10