Wegner


Colouring the square of a planar graph ★★

Author(s): Wegner

\begin{conjecture} Let $G$ be a planar graph of maximum degree $\Delta$. The chromatic number of its square is \begin{itemize} \item at most $7$ if $\Delta =3$, \item at most $\Delta+5$ if $4\leq\Delta\leq 7$, \item at most $\left\lfloor\frac32\,\Delta\right\rfloor+1$ if $\Delta\ge8$. \end{itemize} \end{conjecture}

Keywords:

Syndicate content