Walk-powers and homomorphism bound of planar graphs

Abstract

As an extension of the Four-Color Theorem it is conjectured that every planar graph of odd-girth at least $2k+1$ admits a homomorphism to $P{C}_{2k}=({\mathbb{Z}}_2^{2k},\{e_1,e_2,...,e_{2k},J\})$ where $e_i$'s are standard basis and $J$ is all 1 vector. Noting that $P{C}_{2k}$ itself is of odd-girth $2k+1$, in this work we show that if the conjecture is true, then $P{C}_{2k}$ is an optimal such a graph both with respect to number of vertices and number of edges. The result is obtained using the notion of walk-power of graphs and their clique numbers. An analogous result is proved for bipartite signed planar graphs of unbalanced-girth $2k$. The work is presented on a uniform frame work of planar consistent signed graphs.