Equitable partition of planar graphs

Ringi Kim; Sang-il Oum; Xin Zhang

doi:10.1016/j.disc.2021.112351

paper

Equitable partition of planar graphs

arXiv:1907.09911 · doi:10.1016/j.disc.2021.112351

Abstract

An equitable $k$ -partition of a graph $G$ is a collection of induced subgraphs $(G [V_{1}], G [V_{2}], \dots, G [V_{k}])$ of $G$ such that $(V_{1}, V_{2}, \dots, V_{k})$ is a partition of $V (G)$ and $- 1 \leq ∣ V_{i} ∣ - ∣ V_{j} ∣ \leq 1$ for all $1 \leq i < j \leq k$ . We prove that every planar graph admits an equitable $2$ -partition into $3$ -degenerate graphs, an equitable $3$ -partition into $2$ -degenerate graphs, and an equitable $3$ -partition into two forests and one graph.

12 pages; revised; accepted to Discrete Math

References in corpus (1)

Equitable partition of graphs into induced forests