The 3-colorability problem is known to be NP-complete in the class of graphs with maximum degree four. On the other hand, due to the celebrated theorem of Brooks, the problem has a polynomial-time solution for graphs with maximum degree three. To make the complexity gap more precise, we study a family of intermediate graph classes between these two extremes and classify all of them according to the computational complexity of the problem. In particular, we generalize Brooks's theorem in the case of 3-colorability to a larger class by showing that every connected graph in that class is 3-colorable, unless it is a complete graph on four vertices.

The aim of this paper is to introduce a general framework for various results regarding constructions of matroids and (generalized) polymatroids---for instance, the basic operations on (generalized) polymatroids and constructions of transversal matroids, gammoids, and their generalizations. All of them are covered by the following theorem: If $\Bbb P_1$ and $\Bbb P_2$ are generalized polymatroids in $\Bbb R^n\oplus\Bbb R^m$ and $\Bbb R^m$, respectively, and $\Bbb P'_1$ is the set of the vectors from $\Bbb P_1$ whose projections to $\Bbb R^m$ are in $\Bbb P_2$, then the projection of $\Bbb P'_1$ to $\Bbb R^n$ is a generalized polymatroid. An equivalent statement is obtained using a flow model that has many common features with the concept of group-valued flows.