Facial Colorings of Plane Graphs

NEW

Problem: Reconstructed statement: For every finite 2-edge-connected plane graph $G$, let $\operatorname{fep}(G)$ be the least $k$ such that $E(G)$ can be colored with colors $1,\dots,k$ so that no facial trail of length at most $i+1$ contains two distinct edges colored $i$. Equivalently, every facial trail containing two edges of color $i$ has length at least $i+2$. The conjecture asks whether there is an absolute constant $K$ with $\operatorname{fep}(G)\le K$ for all such $G$.

Result: The conjecture is true. In fact, one may take any $K$ with

for example $K=\lceil e^{25}\rceil$.

Proof. Fix such a $K$, and color each edge independently with color $i\in\{1,\dots,K\}$ with probability

For every color $i$ and every unordered pair of distinct edges $\{a,b\}$ contained together in some facial trail of length at most $i+1$, let $A_{a,b,i}$ be the bad event that both $a,b$ receive color $i$. Avoiding all bad events is exactly a facial $K$-packing edge-coloring.

Use the usual Lovász local lemma dependency graph: two bad events are adjacent if their edge-pairs intersect. For a fixed edge $a$ and fixed $j$, there are at most $4j$ edges $b$ that lie with $a$ on a facial trail of length at most $j+1$: the edge $a$ has two facial sides, and on each side there are at most $j$ edges in each direction. Hence a bad event has at most $8j$ neighbors of color $j$.

Set

Since $H_K\ge25$, all $x_j<1$. For any bad event of color $i$,

Moreover,

using $H_K\ge25$ and $e<3$. Thus

Therefore

so the asymmetric Lovász local lemma gives positive probability that no bad event occurs. Hence $G$ has a facial $K$-packing edge-coloring.

Thus $\operatorname{fep}(G)\le \lceil e^{25}\rceil$ for every finite 2-edge-connected plane graph $G$.

Citation: Uses the standard asymmetric Lovász local lemma. Definition of facial packing edge-coloring matches Czap–Jendrol’, “Facial packing edge-coloring of plane graphs,” Discrete Applied Mathematics 213 (2016), 71–75.