Face $S_3$-colorings and Petrie monochromatic circuits for efficient total arc colorings of cubic maps of girth 4

Abstract

Let $G=(V(G),E(G))$ be a finite connected simple cubic graph. A total coloring $\mu :V(G)\cup E(G)\to \{0,1,2,3\}$ is efficient if each color yields an efficient dominating set, where the efficient dominating condition applies to the restriction of each color class to $V(G)$. If the girth of $G$ is 4 and $\mu$ uses 4 colors both on vertices and edges of each 4-cycle, then $\mu$ is an ETGC. Maps $M(G)$ of such $G$ are considered on the orientable surfaces. We show that a necessary condition for ETGCs to exist on $M(G)$ is that they have only face lengths divisible by 4. When such ETGCs exist, for which 7 constructive tools are provided, the faces of the maps $M(G)$ possessing them are shown to be colorable by the group $S_3$ of 3-permutations whenever the ETGCs are periodic. For the vertex coloring of each ETGC, there are two orthogonal edge colorings: directed and reversed. There are two injections into the set of face $S_3$-colorings: one from the set of periodic directed ETGCs, the other from that of periodic reversed ETGCs. We take each edge of $G$ as a pair of opposite arcs. Let $A^{\leftrightarrow }$ be the set of such arcs and let $G^{\leftrightarrow }$ be the digraph with vertex set $V(G)$ and arc set $A^{\leftrightarrow }$. A ditotal coloring ${\mu }^{\leftrightarrow }$ of $G^{\leftrightarrow }$ is given by having bijections via ${\mu }^{\leftrightarrow }$ from the sets formed by: {\bf(a)} each vertex and the arcs arriving to it; {\bf(b)} each vertex and the arcs departing from it; {\bf(c)} each vertex and its neighbors; {\bf(d)} each pair of oppositely oriented arcs of an edge and its end-vertices. Then, each ETGC of an $M(G)$ has a ditotal coloring. The Petrie dual of the resulting map $M(G^{\leftrightarrow })$ is formed by monochromatic directed cycles.

arXiv comment37 pages, 24 figures