Relaxed chromatic numbers of graphs (Q1323496)

Let \(P\) be a family of graphs; the \(P\) chromatic number \(\chi_ P (G)\) of a graph \(G\) is defined to be the smallest number of classes into which \(V(G)\) can be partitioned so that each class induces a subgraph in \(P\). (Thus if \(P\) is the family of empty graphs, we regain the usual chromatic number.) The authors study this ``relaxed'' parameter, for hereditary families \(P\) of two types: (1) graphs containing no subgraph of a fixed graph \(H\); (2) graphs which are disjoint unions of subgraphs of \(H\). Some results on the usual chromatic number are generalized, and \(\chi_ P (G)\) is computed for special choices of \(P\) on special classes of graphs.