# Vertex coloring

## Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

Let $r$ be a positive integer. We say that a graph $G$ is strongly $r$-colorable if for every partition of the vertices to sets of size at most $r$ there is a proper $r$-coloring of $G$ in which the vertices in each set of the partition have distinct colors.

\begin{conjecture} If $\Delta$ is the maximal degree of a graph $G$, then $G$ is strongly $2 \Delta$-colorable. \end{conjecture}

Keywords: strong coloring

## Reed's omega, delta, and chi conjecture ★★★

Author(s): Reed

For a graph $G$, we define $\Delta(G)$ to be the maximum degree, $\omega(G)$ to be the size of the largest \Def[clique]{clique (graph theory)} subgraph, and $\chi(G)$ to be the chromatic number of $G$.

\begin{conjecture} $\chi(G) \le \ceil{\frac{1}{2}(\Delta(G)+1) + \frac{1}{2}\omega(G)}$ for every graph $G$. \end{conjecture}

Keywords: coloring

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

Author(s): Ghebleh; Zhu

\begin{problem} Does every triangle-free planar graph of maximum degree three have circular chromatic number at most $\frac{20}{7}$? \end{problem}

Keywords: circular coloring; planar graph; triangle free

## Oriented chromatic number of planar graphs ★★

Author(s):

An oriented colouring of an oriented graph is assignment $c$ of colours to the vertices such that no two arcs receive ordered pairs of colours $(c_1,c_2)$ and $(c_2,c_1)$. It is equivalent to a homomorphism of the digraph onto some tournament of order $k$.

\begin{problem} What is the maximal possible \Def[oriented chromatic number]{Oriented_coloring} of an oriented planar graph? \end{problem}

Keywords: oriented coloring; oriented graph; planar graph

## Coloring and immersion ★★★

Author(s): Abu-Khzam; Langston

\begin{conjecture} For every positive integer $t$, every (loopless) graph $G$ with $\chi(G) \ge t$ immerses $K_t$. \end{conjecture}

Keywords: coloring; complete graph; immersion

## Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The \emph{Odd Distance Graph}, denoted ${\mathcal O}$, is the graph with vertex set ${\mathbb R}^2$ and two points adjacent if the distance between them is an odd integer.

\begin{question} Is $\chi({\mathcal O}) = \infty$? \end{question}

Keywords: coloring; geometric graph; odd distance

## Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

\begin{conjecture} Let $G$ be a simple graph with $n$ vertices and list chromatic number $\chi_\ell(G)$. Suppose that $0\leq t\leq \chi_\ell$ and each vertex of $G$ is assigned a list of $t$ colors. Then at least $\frac{tn}{\chi_\ell(G)}$ vertices of $G$ can be colored from these lists. \end{conjecture}

Keywords: list assignment; list coloring

## Partial List Coloring ★★★

Let $G$ be a simple graph, and for every list assignment $\mathcal{L}$ let $\lambda_{\mathcal{L}}$ be the maximum number of vertices of $G$ which are colorable with respect to $\mathcal{L}$. Define $\lambda_t = \min{ \lambda_{\mathcal{L}} }$, where the minimum is taken over all list assignments $\mathcal{L}$ with $|\mathcal{L}| = t$ for all $v \in V(G)$.

\begin{conjecture} [2] Let $G$ be a graph with list chromatic number $\chi_\ell$ and $1\leq r\leq s\leq \chi_\ell$. Then $\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.$ \end{conjecture}

Keywords: list assignment; list coloring

## Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

\begin{conjecture} If $G,H$ are simple finite graphs, then $\chi(G \times H) = \min \{ \chi(G), \chi(H) \}$. \end{conjecture}

Here $G \times H$ is the \Def[tensor product]{tensor product of graphs} (also called the direct or categorical product) of $G$ and $H$.

## Counting 3-colorings of the hex lattice ★★

Author(s): Thomassen

\begin{problem} Find $\lim_{n \rightarrow \infty} (\chi( H_n , 3)) ^{ 1 / |V(H_n)| }$. \end{problem}

Keywords: coloring; Lieb's Ice Constant; tiling; torus

## Circular colouring the orthogonality graph ★★

Author(s): DeVos; Ghebleh; Goddyn; Mohar; Naserasr

Let ${\mathcal O}$ denote the graph with vertex set consisting of all lines through the origin in ${\mathbb R}^3$ and two vertices adjacent in ${\mathcal O}$ if they are perpendicular.

\begin{problem} Is $\chi_c({\mathcal O}) = 4$? \end{problem}

## Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph $G$ is called double-critical, if removing any pair of adjacent vertexes lowers the \Def{chromatic number} by two.

\begin{conjecture} $K_n$ is the only $n$-chromatic double-critical graph \end{conjecture}

Keywords: coloring; complete graph

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

Author(s): Kostochka; Reed

\begin{conjecture} A triangle-free graph with maximum degree $\Delta$ has chromatic number at most $\ceil{\frac{\Delta}{2}}+2$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords: chromatic number; girth; maximum degree; triangle free

## Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family ${\mathcal F}$ of graphs is $\chi$-\emph{bounded} if there exists a function $f: {\mathbb N} \rightarrow {\mathbb N}$ so that every $G \in {\mathcal F}$ satisfies $\chi(G) \le f (\omega(G))$.

\begin{conjecture} For every fixed tree $T$, the family of graphs with no induced subgraph isomorphic to $T$ is $\chi$-bounded. \end{conjecture}

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

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

Author(s): Geelen

\begin{question} Is every proper vertex-minor closed class of graphs chi-bounded? \end{question}

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

## Mixing Circular Colourings ★

Author(s): Brewster; Noel

\begin{question} Is $\mathfrak{M}_c(G)$ always rational? \end{question}

Keywords: discrete homotopy; graph colourings; mixing

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

Author(s): Noel

\begin{conjecture} If $G$ is a $k$-chromatic graph on at most $mk$ vertices, then $\text{ch}(G)\leq \text{ch}(K_{m*k})$. \end{conjecture}

## Melnikov's valency-variety problem ★

Author(s): Melnikov

\begin{problem} The valency-variety $w(G)$ of a graph $G$ is the number of different degrees in $G$. Is the chromatic number of any graph $G$ with at least two vertices greater than $$\ceil{ \frac{\floor{w(G)/2}}{|V(G)| - w(G)} } ~ ?$$ \end{problem}

Keywords:

## Earth-Moon Problem ★★

Author(s): Ringel

\begin{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 ? \end{problem}

Keywords:

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

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

\begin{conjecture} Every planar graph is acyclically 5-choosable. \end{conjecture}

Keywords: