## Three-ell-plus-one Conjecture

This problem has been kindly submitted by Daniel Kral, Tomas Madaras and
Riste Škrekovski.

Let G be a plane graph and let *l* be a nonnegative integer. A coloring
of vertices of G is *l*-facial, if any two distinct vertices that are at
most *l* apart on some facial walk are colored differently.

**(3***l *+ 1)-Conjecture (Kral, Madaras, and
Škrekovski): Every plane
graph has an *l*-facial coloring with 3*l*+1 colors.

The above conjecture is trivially true for *l *= 0 and the case *l *
= 1 is equivalent to the 4CT. It is open for each *l *> 1. For *l *=
2, it implies the Wegner conjecture that the square of a subcubic planar graph
is 7-colorable (see Problem 2.18 in Jensen & Toft's book). The above conjecture
also implies the Cyclic Coloring Conjecture when maximum face size is odd (see the first
question of Problem 2.5 in Jensen & Toft's book).

If the conjecture is true, then the bound 3*l *+ 1 is sharp. Just
consider the graph K_{4}, where all three edges at one vertex are
replaced by paths of length *l *+ 1. This graph has 3*l *+ 1 vertices
and any two must be assigned distinct colors.

Send comments to Bojan.Mohar@uni-lj.si

##### Revised: November 22, 2004.