On irredundance coloring and irredundance compelling coloring of graphs
David Ashok Kalarkop, Michael A. Henning, I. Sahul Hamid, Pawaton Kaemawichanurat · Discrete Applied Mathematics · 2025
An irredundance coloring of a graph G is a proper coloring admitting a maximal irredundant set all of whose vertices receive 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 χ i ( G ) . An irredundance compelling coloring of G is a proper coloring of G in which every rainbow committee (a set consisting of one 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 χ i r c ( G ) . We make a detailed study of χ i ( G ) , χ i r c ( G ) , derive bounds on these parameters and characterize extremal graphs attaining the bounds.