Extremal results on defective colorings of graphs

A 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 χ₀(G), χ₁(G), χ₂(G),...; it is an open question whether this condition is also sufficient.