$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 3Delta^*/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 $3ell + 1$ colors for an $ell$-facial edge-coloring. Therefore it is also conjectured that $3ell + 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 Luv{z}ar.

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

Everyone is welcome and encouraged to attend.