zbMATH — the first resource for mathematics

Improper coloring of graphs on surfaces. (English) Zbl 1418.05062
Given a set of \(k\) integers, a graph \(G\) is said to be \((d_{1}, d_{2}, \dots, d_{k})\)-colorable if the vertex set \(V(G)\) can be partitioned into \(k\) subsets \(V_{1}, V_{2}, \dots, V_{k}\) such that for each index \(i \in \{1, 2, \dots, k\}\), the subgraph induced on \(V_{i}\) has maximum degree at most \(d_{i}\).
As an extension of the four color theorem and subsequent results, the authors prove the following main result.
Theorem. Every graph embeddable on a surface with Euler genus \(g > 0\) is \((0, 0, 0, 9g - 4)\)-colorable and \((2, 2, 9g - 4)\)-colorable.
It is also shown that such graphs are \((0, 0, O(\sqrt{g}), O(\sqrt{g}))\)-colorable and \((2, O(\sqrt{g}), O(\sqrt{g}))\)-colorable. Furthermore, if such a graph is also triangle-free, then it is shown to be \((0, 0, O(g))\)-colorable.
The proof of the main result uses induction on the genus \(g\) where the induction hypothesis is “refined” to also assume there is a subgraph with additional useful properties.
Other proofs use contradiction and a discharging argument in which vertices and faces of the embedded graph receive an initial charge based on their degrees. Using Euler’s formula, the total initial charge is easily calculated. Charges are dissipated following a set of discharging rules and the resulting charge is analyzed, to arrive at a contradiction.

05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C07 Vertex degrees
Full Text: DOI