Point partition numbers: decomposable and indecomposable critical graphs

Abstract

Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number ${\chi }_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 ${\chi }_1$ is the chromatic number and ${\chi }_2$ is the point aboricity. The point partition number ${\chi }_t$ with $t\ge 1$ was introduced by Lick and White. A graph $G$ is called ${\chi }_t$-critical if every proper subgraph $H$ of $G$ satisfies ${\chi }_t(H)<{\chi }_t(G)$. In this paper we prove that if $G$ is a ${\chi }_t$-critical graph whose order satisfies $|G|\le 2{\chi }_t(G)-2$, then $G$ can be obtained from two non-empty disjoint subgraphs $G_1$ and $G_2$ by adding $t$ edges between any pair $u,v$ of vertices with $u\in V(G_1)$ and $v\in V(G_2)$. Based on this result we establish the minimum number of edges possible in a ${\chi }_t$-critical graph $G$ of order $n$ and with ${\chi }_t(G)=k$, provided that $n\le 2k-1$ and $t$ is even. For $t=1$ the corresponding two results were obtained in 1963 by Tibor Gallai.