\(n\)-tuple coloring of planar graphs with large odd girth (Q1348656)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(n\)-tuple coloring of planar graphs with large odd girth |
scientific article |
Statements
\(n\)-tuple coloring of planar graphs with large odd girth (English)
0 references
14 May 2002
0 references
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.
0 references
planar graph
0 references
odd girth
0 references
homomorphism
0 references
Kneser graph
0 references