# 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.

**Conjecture**If is the maximal degree of a graph , then is strongly -colorable.

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 .

**Conjecture**for every graph .

Keywords: coloring

## Circular coloring triangle-free subcubic planar graphs ★★

**Problem**Does every triangle-free planar graph of maximum degree three have circular chromatic number at most ?

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 .

**Problem**What is the maximal possible oriented chromatic number of an oriented planar graph?

Keywords: oriented coloring; oriented graph; planar graph

## Coloring and immersion ★★★

Author(s): Abu-Khzam; Langston

**Conjecture**For every positive integer , every (loopless) graph with immerses .

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.

**Question**Is ?

Keywords: coloring; geometric graph; odd distance

## Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

**Conjecture**Let be a simple graph with vertices and list chromatic number . Suppose that and each vertex of is assigned a list of colors. Then at least vertices of can be colored from these lists.

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 .

**Conjecture**[2] Let be a graph with list chromatic number and . Then

Keywords: list assignment; list coloring

## Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

**Conjecture**If are simple finite graphs, then .

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

**Problem**Find .

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.

**Problem**Is ?

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.

**Conjecture**is the only -chromatic double-critical graph

Keywords: coloring; complete graph

## Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

**Conjecture**A triangle-free graph with maximum degree has chromatic number at most .

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 .

**Conjecture**For every fixed tree , the family of graphs with no induced subgraph isomorphic to is -bounded.

Keywords: chi-bounded; coloring; excluded subgraph; tree

## Are vertex minor closed classes chi-bounded? ★★

Author(s): Geelen

**Question**Is every proper vertex-minor closed class of graphs chi-bounded?

Keywords: chi-bounded; circle graph; coloring; vertex minor

## Mixing Circular Colourings ★

**Question**Is always rational?

Keywords: discrete homotopy; graph colourings; mixing

## Choice Number of k-Chromatic Graphs of Bounded Order ★★

Author(s): Noel

**Conjecture**If is a -chromatic graph on at most vertices, then .

Keywords: choosability; complete multipartite graph; list coloring

## Melnikov's valency-variety problem ★

Author(s): Melnikov

**Problem**The valency-variety of a graph is the number of different degrees in . Is the chromatic number of any graph with at least two vertices greater than

Keywords:

## Earth-Moon Problem ★★

Author(s): Ringel

**Problem**What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?

Keywords:

## Acyclic list colouring of planar graphs. ★★★

Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena

**Conjecture**Every planar graph is acyclically 5-choosable.

Keywords: