Near-complete multipartite graphs and forbidden induced subgraphs Original Research Article

A proper vertex k-coloring C1,C2,…,Ck of a graph G is called l-bounded (l⩾0) if |Ci⧹N(u)|⩽l for each i=1,2,…,k and each vertex u∈VG⧹Ci, where N(u) is the neighborhood of u. Let C(k,l) be the class of all graphs having an l-bounded k-coloring (k⩾1 and l⩾0). We prove that every class C(k,l) has a finite forbidden induced subgraph characterization. This result implies the existence of polynomial algorithms for recognition of C(k,l). The set of all 14 minimal forbidden induced subgraphs for C(3,1) is found.