Graph-theory open problems

Coloring

subject tag · 65 problems

Title Source Status Imp. Posted
5-flow conjecture opg partial ★★★★ 2007-03-07
Acyclic list colouring of planar graphs. opg partial ★★★ 2013-03-07
Erdős–Faber–Lovász conjecture opg partial ★★★ 2013-08-22
Graphs with a forbidden induced tree are chi-bounded opg partial ★★★ 2009-05-16
Edge list coloring conjecture opg open ★★★ 2008-09-25
Goldberg's conjecture opg solved ★★★ 2008-10-04
Hedetniemi's Conjecture opg disproved ★★★ 2008-05-25
Partial List Coloring opg partial ★★★ 2008-05-05
Partial List Coloring opg partial ★★★ 2008-05-12
Seymour's r-graph conjecture opg solved ★★★ 2008-10-03
Total Colouring Conjecture opg partial ★★★ 2008-06-04
3-flow conjecture opg partial ★★★ 2007-03-07
4-flow conjecture opg partial ★★★ 2007-03-07
Bouchet's 6-flow conjecture opg partial ★★★ 2007-03-07
Coloring and immersion opg partial ★★★ 2007-09-04
Coloring the Odd Distance Graph opg solved ★★★ 2007-10-03
Graceful Tree Conjecture opg partial ★★★ 2007-07-13
Jaeger's modular orientation conjecture opg disproved ★★★ 2007-03-07
Linial-Berge path partition duality opg partial ★★★ 2007-03-27
Mapping planar graphs to odd cycles opg partial ★★★ 2007-06-24
Pentagon problem opg open ★★★ 2007-03-24
Petersen coloring conjecture opg partial ★★★ 2007-03-07
Reed's omega, delta, and chi conjecture opg partial ★★★ 2007-05-22
Strong colorability opg partial ★★★ 2007-03-27
Circular flow number of regular class 1 graphs opg disproved ★★ 2015-08-05
Cycles in Graphs of Large Chromatic Number opg partial ★★ 2015-09-20
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
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
Earth-Moon Problem opg partial ★★ 2013-03-06
List chromatic number and maximum degree of bipartite graphs opg partial ★★ 2013-03-12
List Total Colouring Conjecture opg open ★★ 2013-08-29
Strong edge colouring conjecture opg partial ★★ 2013-03-01
Weighted colouring of hexagonal graphs. opg partial ★★ 2013-03-13
Good Edge Labelings opg partial ★★ 2011-06-30
Algorithm for graph homomorphisms opg partial ★★ 2010-07-08
Are vertex minor closed classes chi-bounded? opg solved ★★ 2009-05-16
Bounding the chromatic number of triangle-free graphs with fixed maximum degree opg open ★★ 2009-04-17
Double-critical graph conjecture opg partial ★★ 2009-01-18
4-regular 4-chromatic graphs of high girth opg open ★★ 2008-06-18
Circular colouring the orthogonality graph opg open ★★ 2008-09-23
Counting 3-colorings of the hex lattice opg open ★★ 2008-07-05
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
List colorings of edge-critical graphs opg open ★★ 2007-06-12
Oriented chromatic number of planar graphs opg partial ★★ 2007-08-04
Packing T-joins opg partial ★★ 2007-03-07
Real roots of the flow polynomial opg disproved ★★ 2007-03-07
The three 4-flows conjecture opg open ★★ 2007-03-07
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
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