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

$$H_K=\sum_{j=1}^K\frac1j\ge 25,$$

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

$$p_i=\frac{1}{iH_K}.$$

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

$$x_j=e\,p_j^2=\frac{e}{j^2H_K^2}.$$

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

$$\prod_{B\sim A}(1-x_B) \ge \prod_{j=1}^K(1-x_j)^{8j}.$$

Moreover,

$$-\log\prod_{j=1}^K(1-x_j)^{8j} \le \frac{8}{1-e/H_K^2}\sum_{j=1}^K jx_j = \frac{8e}{H_K(1-e/H_K^2)} <1,$$

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

$$\prod_{B\sim A}(1-x_B)\ge e^{-1}.$$

Therefore

$$\Pr(A)=p_i^2\le x_i\prod_{B\sim A}(1-x_B),$$

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.