Maximal independent sets in minimum colorings

S. Arumugam, Teresa W. Haynes, Michael A. Henning, Yared Nigussie

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

Every graph G contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set (equivalently, a dominating set) in G. Among all such minimum vertex-colorings of the vertices of G, a coloring with the maximum number of color classes that are dominating sets in G is called a dominating-χ-coloring of G. The number of color classes that are dominating sets in a dominating-χ-coloring of G is defined to be the dominating-χ-color number of G. In this paper, we continue to investigate the dominating-χ-color number of a graph first defined and studied in [1].

Original languageEnglish
Pages (from-to)1158-1163
Number of pages6
JournalDiscrete Mathematics
Volume311
Issue number13
DOIs
Publication statusPublished - 6 Jul 2011

Keywords

  • Chromatic number
  • Coloring
  • Dom-color number
  • Dominating-χ-color number
  • Domination number
  • Maximal independent set

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Maximal independent sets in minimum colorings'. Together they form a unique fingerprint.

Cite this