Home » Subject » Graph Theory

Coloring

Also see: Graph Theory » Topological G.T. » Coloring
Titlesort iconAuthor(s)Imp.¹Rec.²SubtopicPosted by
Graceful Tree Conjecture✭✭✭0Labelingkintali
2-colouring a graph without a monochromatic maximum cliqueHoang; McDiarmid✭✭0Vertex coloringJon Noel
3-flow conjectureTutte✭✭✭0Nowhere-zero flowsmdevos
4-flow conjectureTutte✭✭✭0Nowhere-zero flowsmdevos
4-regular 4-chromatic graphs of high girthGrunbaum✭✭0mdevos
5-flow conjectureTutte✭✭✭✭0Nowhere-zero flowsmdevos
A generalization of Vizing's Theorem?Rosenfeld✭✭0Edge coloringmdevos
A homomorphism problem for flowsDeVos✭✭0Nowhere-zero flowsmdevos
Acyclic edge-colouringFiamcik✭✭0Edge coloringmdevos
Acyclic list colouring of planar graphs.Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena✭✭✭0Vertex coloringfhavet
Algorithm for graph homomorphismsFomin; Heggernes; Kratsch✭✭0Homomorphismsjfoniok
Antichains in the cycle continuous orderDeVos✭✭0Nowhere-zero flowsmdevos
Are vertex minor closed classes chi-bounded?Geelen✭✭0Vertex coloringmdevos
Bouchet's 6-flow conjectureBouchet✭✭✭0Nowhere-zero flowsmdevos
Bounding the chromatic number of triangle-free graphs with fixed maximum degreeKostochka; Reed✭✭0Vertex coloringAndrew King
Bounding the on-line choice number in terms of the choice numberZhu✭✭1Vertex coloringJon Noel
Choice Number of k-Chromatic Graphs of Bounded OrderNoel✭✭1Vertex coloringJon Noel
Choosability of Graph PowersNoel✭✭1Vertex coloringJon Noel
Circular choosability of planar graphsMohar✭0Homomorphismsrosskang
Circular coloring triangle-free subcubic planar graphsGhebleh; Zhu✭✭0Vertex coloringmdevos
Circular colouring the orthogonality graphDeVos; Ghebleh; Goddyn; Mohar; Naserasr✭✭0Vertex coloringmdevos
Circular flow number of regular class 1 graphsSteffen✭✭0Nowhere-zero flowsEckhard Steffen
Coloring and immersionAbu-Khzam; Langston✭✭✭1Vertex coloringmdevos
Coloring the Odd Distance GraphRosenfeld✭✭✭0Vertex coloringmdevos
Coloring the union of degenerate graphsTarsi✭✭0fhavet
Colouring the square of a planar graphWegner✭✭0Vertex coloringfhavet
Cores of Cayley graphsSamal✭✭0HomomorphismsRobert Samal
Counting 3-colorings of the hex latticeThomassen✭✭0Vertex coloringmdevos
Cycles in Graphs of Large Chromatic NumberBrewster; McGuinness; Moore; Noel✭✭0Vertex coloringJon Noel
Double-critical graph conjectureErdos; Lovasz✭✭0Vertex coloringDFR
Earth-Moon ProblemRingel✭✭1Vertex coloringfhavet
Edge list coloring conjecture✭✭✭0Edge coloringtchow
Erdős–Faber–Lovász conjectureErdos; Faber; Lovasz✭✭✭0Vertex coloringJon Noel
Goldberg's conjectureGoldberg✭✭✭0Edge coloringmdevos
Good Edge LabelingsAraújo; Cohen; Giroire; Havet✭✭0LabelingDOT
Graphs with a forbidden induced tree are chi-boundedGyarfas✭✭✭0Vertex coloringmdevos
Hedetniemi's ConjectureHedetniemi✭✭✭0Vertex coloringmdevos
Jaeger's modular orientation conjectureJaeger✭✭✭0Nowhere-zero flowsmdevos
Linial-Berge path partition dualityBerge; Linial✭✭✭0berger
List chromatic number and maximum degree of bipartite graphsAlon✭✭0Vertex coloringfhavet
List colorings of edge-critical graphsMohar✭✭0Edge coloringRobert Samal
List Colourings of Complete Multipartite Graphs with 2 Big PartsAllagan✭✭1Vertex coloringJon Noel
List Hadwiger ConjectureKawarabayashi; Mohar✭✭0Vertex coloringDavid Wood
List Total Colouring ConjectureBorodin; Kostochka; Woodall✭✭0Jon Noel
Mapping planar graphs to odd cyclesJaeger✭✭✭0Homomorphismsmdevos
Melnikov's valency-variety problemMelnikov✭0Vertex coloringasp
Mixing Circular ColouringsBrewster; Noel✭1Vertex coloringJon Noel
Oriented chromatic number of planar graphs✭✭0Vertex coloringRobert Samal
Packing T-joinsDeVos✭✭0Edge coloringmdevos
Partial List ColoringAlbertson; Grossman; Haas✭✭✭0Vertex coloringIradmusa

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

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

Syndicate content