A proper coloring of a graph is a labeled partition of its vertices into parts which are independent sets. In this paper, given a positive integer j and a family F of connected graphs, we consider proper colorings in which we require that the union of any j color classes induces a subgraph which has no copy of any member of F. This generalizes some well-known types of proper colorings like acyclic colorings (where j = 2 and Fis the collection of all even cycles) and star colorings (where j = 2 and Fconsists of just a path on 4 vertices), etc. For this type of coloring, we obtain an upper bound of O(d (k - 1)/(k - j)) on the minimum number of colors sufficient to obtain such a coloring. Here, d refers to the maximum degree of the graph and k is the size of the smallest member of F. For the case of j = 2, we also obtain lower bounds on the minimum number of colors needed in the worst case. As a corollary, we obtain bounds on the minimum number of colors sufficient to obtain proper colorings in which the union of any j color classes is a graph of bounded treewidth. In particular, using O(d8/7) colors, one can obtain a proper coloring of the vertices of a graph so that the union of any two color classes has treewidth at most 2. We also show that this bound is tight within a multiplicative factor of O((logd)1/7). We also consider generalizations where we require simultaneously for several pairs (j i, Fi) (i = 1, ..., l) that the union of any ji color classes has no copy of any member of Fi and obtain upper bounds on the corresponding chromatic numbers. © 2011 Wiley Periodicals, Inc.