Frugal coloring in planar graphs with maximum degree 4 and 5

@misc{bresar2026frugal,
  title = {{Frugal coloring in planar graphs with maximum degree 4 and 5}},
  author = {Boštjan Brešar and Přemysl Holub and Marko Jakovac and Petra Melicharová},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.12640},
  eprint = {2610.12640},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.12640},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Frugal coloring in planar graphs with maximum degree 4 and 5
AU  - Boštjan Brešar
AU  - Přemysl Holub
AU  - Marko Jakovac
AU  - Petra Melicharová
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.12640
UR  - https://arxiv.org/abs/2610.12640
AB  - A proper coloring of vertices of a graph G is called t-frugal if no color appears more than t times in the neighborhood of any vertex of G. While $1$-frugal coloring coincides with $2$-distance coloring, we study $2$-frugal colorings of planar graphs with maximum degree $4$ and $5$, respectively. We prove that every planar graph with maximum degree $4$ admits a $2$-frugal coloring with $7$ colors, while a planar graph with maximum degree $5$ admits a $2$-frugal coloring with $10$ colors. The results present variations of parts of the famous Wegner's conjecture, which for planar graphs with maximum degree Δ∈{4,…,7} states that their $2$-distance chromatic number is at most Δ+5.
ER  -