The chromatic number of the square of subcubic planar graphs

NEW

Problem: Reconstructed statement: for every finite simple plane graph $G$ with maximum degree at most $3$, if in the given planar embedding no face has boundary-walk length $5$, then $\chi(G^2)\le 6$, where $G^2$ joins vertices at distance at most $2$ in $G$.

Result: The statement is false.

Construct a plane graph $G$ as follows. Start with vertices

and edges

Embed $x_1x_2x_3$ as the outer triangle and put $z$ inside, with the three length-2 paths $x_i y_i z$. The three bounded faces are the 5-faces

with indices modulo $3$.

Now, inside the face $x_i x_{i+1} y_{i+1} z y_i x_i$, add a new pendant vertex $p_i$ adjacent only to $y_i$. This keeps $\Delta(G)\le 3$: each $y_i$ now has degree $3$, each $p_i$ has degree $1$, and all other original vertices already had degree $3$.

Under the standard plane-graph convention that a bridge is counted twice in the boundary walk of a face, each former 5-face now has boundary length $5+2=7$. The outer face has length $3$. Hence this drawing has no face of length $5$.

But the original seven vertices form a clique in $G^2$. Indeed:

• the $x_i$'s are pairwise adjacent;
• $x_i$ is adjacent to $y_i$ and distance $2$ from $z$;
• $x_i$ is distance $2$ from $y_j$ for $j\ne i$, via $x_j$;
• $y_i$ and $y_j$ are distance $2$ via $z$.

Thus every two of

are at distance at most $2$ in $G$, so $G^2$ contains a $K_7$. Therefore

contradicting the claimed bound $\chi(G^2)\le 6$.

The natural defect is the missing exclusion of bridges/cut-vertices, since pendant edges can destroy facial 5-walks without destroying the $K_7$ in the square.

Citation: Counterexample constructed here; no external resolution used.