Planar graphs with girth at least 5 are (3,4)-colorable

Ilkyoo Choi; Gexin Yu; Xia Zhang

paper

Planar graphs with girth at least 5 are (3,4)-colorable

arXiv:1908.03172

Abstract

A graph is $(d_{1}, \dots, d_{k})$ -colorable if its vertex set can be partitioned into $k$ nonempty subsets so that the subgraph induced by the $i$ th part has maximum degree at most $d_{i}$ for each $i \in {1, \dots, k}$ . It is known that for each pair $(d_{1}, d_{2})$ , there exists a planar graph with girth $4$ that is not $(d_{1}, d_{2})$ -colorable. This sparked the interest in finding the pairs $(d_{1}, d_{2})$ such that planar graphs with girth at least $5$ are $(d_{1}, d_{2})$ -colorable. Given $d_{1} \leq d_{2}$ , it is known that planar graphs with girth at least $5$ are $(d_{1}, d_{2})$ -colorable if either $d_{1} \geq 2$ and $d_{1} + d_{2} \geq 8$ or $d_{1} = 1$ and $d_{2} \geq 10$ . We improve an aforementioned result by providing the first pair $(d_{1}, d_{2})$ in the literature satisfying $d_{1} + d_{2} \leq 7$ where planar graphs with girth at least $5$ are $(d_{1}, d_{2})$ -colorable. Namely, we prove that planar graphs with girth at least $5$ are $(3, 4)$ -colorable.

16 pages, 4 figures