
Vertex coloring
Strong colorability ★★★
Author(s): Aharoni; Alon; Haxell
Let be a positive integer. We say that a graph
is strongly
-colorable if for every partition of the vertices to sets of size at most
there is a proper
-coloring of
in which the vertices in each set of the partition have distinct colors.




Keywords: strong coloring
Reed's omega, delta, and chi conjecture ★★★
Author(s): Reed
For a graph , we define
to be the maximum degree,
to be the size of the largest clique subgraph, and
to be the chromatic number of
.


Keywords: coloring
Circular coloring triangle-free subcubic planar graphs ★★

Keywords: circular coloring; planar graph; triangle free
Oriented chromatic number of planar graphs ★★
Author(s):
An oriented colouring of an oriented graph is assignment of colours to the vertices such that no two arcs receive ordered pairs of colours
and
. It is equivalent to a homomorphism of the digraph onto some tournament of order
.
Keywords: oriented coloring; oriented graph; planar graph
Coloring and immersion ★★★
Author(s): Abu-Khzam; Langston




Keywords: coloring; complete graph; immersion
Coloring the Odd Distance Graph ★★★
Author(s): Rosenfeld
The Odd Distance Graph, denoted , is the graph with vertex set
and two points adjacent if the distance between them is an odd integer.

Keywords: coloring; geometric graph; odd distance
Partial List Coloring ★★★
Author(s): Albertson; Grossman; Haas








Keywords: list assignment; list coloring
Partial List Coloring ★★★
Author(s): Iradmusa
Let be a simple graph, and for every list assignment
let
be the maximum number of vertices of
which are colorable with respect to
. Define
, where the minimum is taken over all list assignments
with
for all
.



![\[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]](/files/tex/47be18e956355dd433b88b66eabf01a9e3ed5f61.png)
Keywords: list assignment; list coloring
Hedetniemi's Conjecture ★★★
Author(s): Hedetniemi


Here is the tensor product (also called the direct or categorical product) of
and
.
Keywords: categorical product; coloring; homomorphism; tensor product
Counting 3-colorings of the hex lattice ★★
Author(s): Thomassen

Keywords: coloring; Lieb's Ice Constant; tiling; torus
Circular colouring the orthogonality graph ★★
Author(s): DeVos; Ghebleh; Goddyn; Mohar; Naserasr
Let denote the graph with vertex set consisting of all lines through the origin in
and two vertices adjacent in
if they are perpendicular.

Keywords: circular coloring; geometric graph; orthogonality
Double-critical graph conjecture ★★
A connected simple graph is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.


Keywords: coloring; complete graph
Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★


Keywords: chromatic number; girth; maximum degree; triangle free
Graphs with a forbidden induced tree are chi-bounded ★★★
Author(s): Gyarfas
Say that a family of graphs is
-bounded if there exists a function
so that every
satisfies
.



Keywords: chi-bounded; coloring; excluded subgraph; tree
Are vertex minor closed classes chi-bounded? ★★
Author(s): Geelen
Keywords: chi-bounded; circle graph; coloring; vertex minor
Mixing Circular Colourings ★

Keywords: discrete homotopy; graph colourings; mixing
Choice Number of k-Chromatic Graphs of Bounded Order ★★
Author(s): Noel




Keywords: choosability; complete multipartite graph; list coloring
Melnikov's valency-variety problem ★
Author(s): Melnikov





Keywords:
Earth-Moon Problem ★★
Author(s): Ringel
Keywords:
Acyclic list colouring of planar graphs. ★★★
Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena
Keywords:
