Crossing numbers and coloring ★★★

Author(s): Albertson

We let $cr(G)$ denote the \Def[crossing number]{crossing number (graph theory)} of a graph $G$.

\begin{conjecture} Every graph $G$ with $\chi(G) \ge t$ satisfies $cr(G) \ge cr(K_t)$. \end{conjecture}

Keywords: coloring; complete graph; crossing number

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

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

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

\begin{conjecture} Every sufficiently large plane triangulation $G$ has a dominating set of size $\le \frac{1}{4} |V(G)|$. \end{conjecture}

Keywords: coloring; domination; multigrid; planar graph; triangulation

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

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

4-regular 4-chromatic graphs of high girth ★★

Author(s): Grunbaum

\begin{problem} Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth? \end{problem}

Keywords: coloring; girth

Coloring random subgraphs ★★

Author(s): Bukh

If $G$ is a graph and $p \in [0,1]$, we let $G_p$ denote a subgraph of $G$ where each edge of $G$ appears in $G_p$ with independently with probability $p$.

\begin{problem} Does there exist a constant $c$ so that ${\mathbb E}(\chi(G_{1/2})) > c \frac{\chi(G)}{\log \chi(G)}$? \end{problem}

Keywords: coloring; random graph

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

Keywords: categorical product; coloring; homomorphism; tensor product

Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph $G$ is $k$-\emph{degenerate} if every subgraph of $G$ has a vertex of degree $\le k$.

\begin{conjecture} Every simple planar graph has a 5-coloring so that for $1 \le k \le 4$, the union of any $k$ color classes induces a $(k-1)$-degenerate graph. \end{conjecture}

Keywords: coloring; degenerate; planar

Syndicate content