Maximal independent sets in minimum colorings. (English) Zbl 1222.05045
Summary: 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-\(\chi \)-coloring of \(G\). The number of color classes that are dominating sets in a dominating-\(\chi \)-coloring of \(G\) is defined to be the dominating-\(\chi \)-color number of \(G\). In this paper, we continue to investigate the dominating-\(\chi \)-color number of a graph first defined and studied in S. Arumugam, I. Sahud Hamid and A.Muthukamatchi, Ramanujan Mathematical Society Lecture Notes Series 7, 195–203 (2008).
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
Keywords:
coloring; chromatic number; domination number; maximal independent set; dominating-\(\chi \)-color number; dom-color numberReferences:
| [1] | Arumugam, S.; Sahul Hamid, I.; Muthukamatchi, A., Independent domination and graph colorings, Ramanujan Mathematical Society Lecture Notes Series, 7, 195-203 (2008) · Zbl 1168.05339 |
| [2] | Chartrand, G.; Zhang, P., Chromatic Graph Theory (2009), Chapman & Hall/CRC: Chapman & Hall/CRC New York · Zbl 1169.05001 |
| [3] | Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002 |
| [4] | (Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs, Advanced Topics (1998), Marcel Dekker: Marcel Dekker New York) · Zbl 0890.05002 |
| [5] | Heggernes, P.; Telle, J. A., Partitioning graphs into generalized dominating sets, Nordic Journal of Computing, 5, 128-142 (1998) · Zbl 0905.68100 |
| [6] | Walikar, H. B.; Acharya, B. D.; Narayankar, Kishori; Shekharappa, H. G., Embedding index of nonindominable graphs, (Arumugam, S.; Acharya, B. D.; Rao, S. B., Procedings of the National Conference on Graphs, Combinatorics, Algorithms and Applications, Arulmigu Kalasalingam College of Engineering, Krishnankoil (2004), Narosa Publishing House: Narosa Publishing House New Delhi), 173-179 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
