\(n\)-tuple coloring of planar graphs with large odd girth (Q1348656): Difference between revisions

An \((n,k)\)-coloring of the graph \(G\) is a mapping \(c:\;V(G) \to {\mathcal{P}}_k(Z_n)\) of the vertex set of \(G\) into the collection of all \(k\)-subsets of \(Z_n = \{0,1,\dots ,n-1\}\) such that \(c(u) \cap c(v) = \emptyset\) if \(uv \in E(G)\); alternatively, this coloring can be viewed as a homomorphism to the Kneser graph \(G_k^n\). The authors prove that every planar graph \(G\) with odd girth at least \(10k-7\;(k \geq 2)\) is \((2k+1,k)\)-colorable. Additionally, if \(G\) is a planar graph with maximum degree \(\Delta(G) \leq 3\) and girth at least \(10k-9\;(k \geq 2)\), then \(G\) is \((2k+1,k)\)-colorable. In the proof, the list of reducible configurations (with respect to \((2k+1,k)\)-coloring) is constructed; assuming a hypothetical counterexample, it is shown that it cannot contain any of those configurations. Then a calculation of Euler contributions of the counterexample contradicts its planarity.