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.
(3l + 1)-Conjecture (Kral, Madaras, and Škrekovski): Every plane graph has an l-facial coloring with 3l+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 3l + 1 is sharp. Just consider the graph K4, where all three edges at one vertex are replaced by paths of length l + 1. This graph has 3l + 1 vertices and any two must be assigned distinct colors.
Send comments to Bojan.Mohar@uni-lj.si