Extremal results on defective colorings of graphs

Marietjie Frick, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

30 Citations (Scopus)


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 χ0(G), χ1(G), χ2(G),...; it is an open question whether this condition is also sufficient.

Original languageEnglish
Pages (from-to)151-158
Number of pages8
JournalDiscrete Mathematics
Issue number1-3
Publication statusPublished - 1 Mar 1994
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Extremal results on defective colorings of graphs'. Together they form a unique fingerprint.

Cite this