## Abstract

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 language | English |
---|---|

Pages (from-to) | 151-158 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 126 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 1 Mar 1994 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics