Home » Subject » Graph Theory

Coloring

Also see: Graph Theory » Topological G.T. » Coloring
TitleAuthor(s)Imp.¹Rec.²SubtopicPosted bysort icon
Bounding the chromatic number of triangle-free graphs with fixed maximum degreeKostochka; Reed✭✭0Vertex coloringAndrew King
Melnikov's valency-variety problemMelnikov✭0Vertex coloringasp
Strong colorabilityAharoni; Alon; Haxell✭✭✭0Vertex coloringberger
Double-critical graph conjectureErdos; Lovasz✭✭0Vertex coloringDFR
Good Edge LabelingsAraújo; Cohen; Giroire; Havet✭✭0LabelingDOT
Strong edge colouring conjectureErdos; Nesetril✭✭0Edge coloringfhavet
Coloring the union of degenerate graphsTarsi✭✭0fhavet
Earth-Moon ProblemRingel✭✭1Vertex coloringfhavet
Acyclic list colouring of planar graphs.Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena✭✭✭0Vertex coloringfhavet
Steinberg's conjecture✭✭✭✭0Vertex coloringfhavet
List chromatic number and maximum degree of bipartite graphsAlon✭✭0Vertex coloringfhavet
Colouring the square of a planar graphWegner✭✭0Vertex coloringfhavet
Weighted colouring of hexagonal graphs.McDiarmid; Reed✭✭0Vertex coloringfhavet
Three-chromatic (0,2)-graphsPayan✭✭0Gordon Royle
Partial List ColoringAlbertson; Grossman; Haas✭✭✭0Vertex coloringIradmusa
Partial List ColoringIradmusa✭✭✭0Vertex coloringIradmusa
Total Colouring ConjectureBehzad✭✭✭0Iradmusa
Algorithm for graph homomorphismsFomin; Heggernes; Kratsch✭✭0Homomorphismsjfoniok
Mixing Circular ColouringsBrewster; Noel✭1Vertex coloringjnoel12
Choice Number of k-Chromatic Graphs of Bounded OrderNoel✭✭1Vertex coloringjnoel12
Choice number of complete multipartite graphs with parts of size 4✭1Vertex coloringjnoel12
On-Line Ohba's ConjectureHuang; Wong; Zhu✭✭1Vertex coloringjnoel12
Bounding the on-line choice number in terms of the choice numberZhu✭✭1Vertex coloringjnoel12
Graceful Tree Conjecture✭✭✭0Labelingkintali
Universal Steiner triple systemsGrannell; Griggs; Knor; Skoviera✭✭0Edge coloringmacajova
5-flow conjectureTutte✭✭✭✭0Nowhere-zero flowsmdevos
4-flow conjectureTutte✭✭✭0Nowhere-zero flowsmdevos
3-flow conjectureTutte✭✭✭0Nowhere-zero flowsmdevos
(2 + epsilon)-flow conjectureGoddyn; Seymour✭✭✭0Nowhere-zero flowsmdevos
Jaeger's modular orientation conjectureJaeger✭✭✭0Nowhere-zero flowsmdevos
Bouchet's 6-flow conjectureBouchet✭✭✭0Nowhere-zero flowsmdevos
The three 4-flows conjectureDeVos✭✭0Nowhere-zero flowsmdevos
A homomorphism problem for flowsDeVos✭✭0Nowhere-zero flowsmdevos
Real roots of the flow polynomialWelsh✭✭0Nowhere-zero flowsmdevos
Unit vector flowsJain✭✭0Nowhere-zero flowsmdevos
Petersen coloring conjectureJaeger✭✭✭0Edge coloringmdevos
Packing T-joinsDeVos✭✭0Edge coloringmdevos
Acyclic edge-colouringFiamcik✭✭0Edge coloringmdevos
A generalization of Vizing's Theorem?Rosenfeld✭✭0Edge coloringmdevos
Antichains in the cycle continuous orderDeVos✭✭0Nowhere-zero flowsmdevos
Reed's omega, delta, and chi conjectureReed✭✭✭0Vertex coloringmdevos
Alon-Saks-Seymour ConjectureAlon; Saks; Seymour✭✭✭0Vertex coloringmdevos
Circular coloring triangle-free subcubic planar graphsGhebleh; Zhu✭✭0Vertex coloringmdevos
Mapping planar graphs to odd cyclesJaeger✭✭✭0Homomorphismsmdevos
Bounding the chromatic number of graphs with no odd holeGyarfas✭✭✭0Vertex coloringmdevos
Coloring and immersionAbu-Khzam; Langston✭✭✭1Vertex coloringmdevos
Coloring the Odd Distance GraphRosenfeld✭✭✭0Vertex coloringmdevos
Coloring squares of hypercubesWan✭✭1Vertex coloringmdevos
Hedetniemi's ConjectureHedetniemi✭✭✭0Vertex coloringmdevos
4-regular 4-chromatic graphs of high girthGrunbaum✭✭0mdevos

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

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

Syndicate content