$\ell$-Facial Edge-Coloring of Plane Graphs

A cyclic coloring of a plane graph is a vertex coloring in which all vertices incident with the same face receive distinct colors.
It is conjectured that every plane graph with maximum face size $\Delta^*$ admits a cyclic edge-coloring with at most $\lfloor 3\Delta^*/2 \rfloor$ colors. Since in the case of plane triangulations this coloring corresponds to a proper coloring, the Four Color Theorem implies the conjecture for $\Delta^* = 3$.

As a generalization of cyclic coloring, a $k$-facial coloring was introduced, where vertices at facial distance at most $k$ receive distinct colors. An open conjecture states that every plane graph admits a $k$-facial coloring with $3k + 1$ colors.

Similarly, an $\ell$-facial edge-coloring of a plane graph is a coloring of its edges such that any two edges at distance at most $\ell$ on a boundary walk of any face receive distinct colors.
One can see that this is a more restricted version of the $k$-facial coloring by taking the medial graph $M(G)$ of a plane graph $G$.

However, there exist graphs that require $3\ell + 1$ colors for an $\ell$-facial edge-coloring. Therefore it is also conjectured that $3\ell + 1$ colors suffice for an $\ell$-facial edge-coloring of any plane graph.
While the cases with $\ell = 1$ and $\ell = 2$ are already established, the general case is still wide open.
In our talk, we give a short history of the topic and present a proof of the case $\ell = 3$.\\

This is a joint work with Borut Lu\v{z}ar.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.