Menu
A vertex \( u \) in a set \( S \) of vertices of a graph \( G \) has a private neighbor (with respect to \( S \)) if either (i) \( u \) has no neighbor in \( S \) or (ii) there exists some vertex \( v \in V(G) – S \) that is a neighbor of \( u \) but not a neighbor of any other vertex in \( S \). A set \( S \) is irredundant in a graph \( G \) if every vertex in \( S \) has a private neighbor. An irredundant \( k \)-coloring of a graph \( G \) is a partition of \( V(G) \) into \( k \) irredundant sets. The minimum \( k \) for which \( G \) has an irredundant \( k \)-coloring is the irredundant chromatic number \( \chi_{ir}(G) \) of \( G \).
A complete coloring of a graph \( G \) is a proper vertex coloring of \( G \) having the property that for every two distinct colors \( i \) and \( j \) used in the coloring, there exist adjacent vertices of \( G \) colored \( i \) and \( j \). The maximum positive integer \( k \) for which \( G \) has a complete \( k \)-coloring is the achromatic number \( \psi(G) \) of \( G \).
A Grundy coloring of a graph \( G \) is a proper vertex coloring of \( G \) having the property that for every two colors (positive integers) \( i \) and \( j \) with \( i < j \), every vertex colored \( j \) has a neighbor colored \( i \). The maximum positive integer \( k \) for which a graph \( G \) has a Grundy \( k \)-coloring is the Grundy number \( \Gamma(G) \) of \( G \). The chromatic number of a graph \( G \) is denoted by \( \chi(G) \). For every graph \( G \), these four coloring parameters satisfy the inequalities \( \chi_{ir}(G) \leq \chi(G) \leq \Gamma(G) \leq \psi(G) \). It is shown that if \( a, b, c \), and \( d \) are integers with \( 2 \leq a \leq b \leq c \leq d \), then there exists a nontrivial connected graph \( G \) with \( \chi_{ir}(G) = a \), \( \chi(G) = b \), \( \Gamma(G) = c \), and \( \psi(G) = d \) if and only if \( d = 2 \) or \( c \neq 2 \).