On generalized graph colorings
Jason I. Brown, Derek Gordon Corneil · Journal of Graph Theory · 1987
Abstract Given a property P , graph G , and k ⩾ 0, a P k ‐coloring is a function π: V(G) → {1, …, k } such that the subgraph induced by each color class has property P; χ(G : P) is the least k , for which G has a P k ‐coloring. We investigate here the theory of P colorings. Generalizations of the wellknown notions of vertex criticality and unique colorability are discussed, and we extend a theorem of Erdös to P chromatic graphs.