Facial colorings using Hall’s Theorem

A vertex coloring of a plane graph is ℓℓ-facial if every two distinct vertices joined by a facial walk of length at most ℓℓ receive distinct colors. It has been conjectured that every plane graph has an ℓℓ-facial coloring with at most 3ℓ+13ℓ+1 colors. We improve the currently best known bound and show that every plane graph has an ℓℓ-facial coloring with at most ⌊7ℓ/2⌋+6⌊7ℓ/2⌋+6 colors. Our proof uses the standard discharging technique, however, in the reduction part we have successfully applied Hall’s Theorem, which seems to be quite an unusual approach in this area.