An equitable $k$-partition of a graph $G$ is a collection of induced subgraphs $(G[V_1],G[V_2],ldots,G[V_k])$ of $G$ such that $(V_1,V_2,ldots,V_k)$ is a partition of $V(G)$ and $-1le |V_i|-|V_j|le 1$ for all $1le i<jle 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.
تحميل البحث