Extremal results on defective colorings of graphs

AbstractA graph is (m,k)-colorable if its vertices can be colored with m colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. The k-defective chromatic number, χk(G), of a graph G is the minimum m for which G is (m,k)-colorable. Among other results, we prove that the smallest orders among all uniquely (m,k)-colorable graphs and all minimal (m,k)-chromatic graphs are m(k+2) − 1 and (m − 1)(k + 1)+1, respectively, and we determine all the extremal graphs in the latter case. We also obtain a necessary condition for a sequence to be a defective chromatic number sequence χ0(G), χ1(G), χ2(G),…; it is an open question whether this condition is also sufficient