Point partition numbers: decomposable and indecomposable critical graphs
Justus von Postel, Thomas Schweser, Michael Stiebitz · arXiv (Cornell University) · 2019
Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number $χ_t(G)$ is the least integer $k$ for which $G$ admits a coloring with $k$ colors such that each color class induces a $(t-1)$-degenerate subgraph of $G$. So $χ_1$ is the chromatic number and $χ_2$ is the point aboricity. The point partition number $χ_t$ with $t\geq 1$ was introduced by Lick and White. A graph $G$ is called $χ_t$-critical if every proper subgraph $H$ of $G$ satisfies $χ_t(H)