Graphs with multi-$4$-cycles and the Barnette's conjecture

Abstract

Let $\mathcal{H}$ denote the family of all graphs with multi-$4$-cycles and suppose that $G\in \mathcal{H}$. Then, $G$ is a bipartite graph with a vertex bipartition $\{V_{\alpha },V_{\beta }\}$. We prove that for every vertex $v\in V_{\beta }$ and for every $2$-colouring $V_{\alpha }\to \{1,2\}$ there exists a $2$-colouring $V_{\beta }\to \{1,2\}$ such that every cycle in $G$ is not monochromatic and $b(v)=1$ ($b(v)=2$). Let now $G$ be a simple even plane triangulation with a vertex $3$-partition $\{V_1,V_2,V_3\}$. Denote by $B_i$, $i=1,2,3$, the set of all vertices in $V_i$ of degree at least $6$ in $G$. Suppose that $G[B_1\cup B_3]$ ($G[B_2\cup B_3]$) is a subgraph of $G$ induced by the set $B_1\cup B_3$ ($B_2\cup B_3$, respectively). Let $G^{\ast }$ be the dual graph of $G$ with the following $3$-face-colouring: a face $f$ of $G^{\ast }$ is coloured with $i$ if and only if the vertex $v=f^{\ast }\in V_i$. We prove that if $H=G[B_1\cup B_3]\cup G[B_2\cup B_3]\in \mathcal{H}$, then, for any edge chosen on a face coloured $3$ and of size at least $6$ in $G^{\ast }$, there exists a Hamilton cycle of $G^{\ast }$ which avoids this edge. Moreover, if every component of $H$ is $2$-connected, then there exists a Hamilton cycle of $G^{\ast }$ such that for every face coloured $3$ it avoids every second edge of this face or it avoids at most two edges of this face.

15 pages