On irredundance coloring and irredundance compelling coloring of graphs

Abstract

Irredundance coloring of $G$ is a proper coloring in which there exists a maximal irredundant set $R$ such that all the vertices of $R$ have different colors. The minimum number of colors required for an irredundance coloring of $G$ is called the irredundance chromatic number of $G$, and is denoted by ${\chi }_i(G)$. Irredundance compelling coloring of $G$ is a proper coloring of $G$ in which every rainbow committee (the set containing a vertex of each color) is an irredundant set of $G$. The maximum number of colors required for an irredundance compelling coloring of $G$ is called the irredundance compelling chromatic number of $G$, and is denoted by ${\chi }_{irc}(G)$. In this paper, we make a detailed study on ${\chi }_i(G)$, ${\chi }_{irc}(G)$ and its relation to other coloring and domination parameters

22 pages, 10 figures