Menu
A Grundy \(k\)-coloring of a graph \(G\) is a proper \(k\)-coloring of vertices in \(G\) using colors \(\{1, 2, \cdots, k\}\) such that for any two colors \(x\) and \(y\), \(x<y\), any vertex colored \(y\) is adjacent to some vertex colored \(x\). The First-Fit or Grundy chromatic number (or simply Grundy number) of a graph \(G\), denoted by \(\Gamma \left(G\right)\), is the largest integer \(k\), such that there exists a Grundy \(k\)-coloring for \(G\). It can be easily seen that \(\Gamma \left(G\right)\) equals to the maximum number of colors used by the greedy (or First-Fit) coloring of \(G\). In this paper, we obtain the Grundy chromatic number of Cartesian Product of path graph, complete graph, cycle graph, complete graph, wheel graph and star graph.
The notion of Grundy colorings was introduced by Patrick Michael Grundy in 1939. Author has dealing with combinatorial games contained ideas that led to the concept of Grundy colorings of graphs.
Definition 1. A Grundy coloring [1,2,3] of a graph \(G\) is a proper vertex coloring of \(G\) (whose colors, as usual, are positive integers) having the property that for every two colors \(x\) and \(y\) with \(x\le y\), every vertex colored \(y\) has a neighbor colored \(x\). Consequently, every Grundy coloring is a complete coloring.
Recall that a greedy coloring [4] \(c\) of a
graph \(G\) is obtained from an
ordering \(\phi: v_1, v_2,\cdots ,
v_n\) of the vertices of \(G\)
in some manner, by defining \(c(v_1) =
1\), and once colors have been assigned to \(v_1, v_2,\cdots , v_p\) for some integer
\(p\) with \(1\leq p \le n\), \(c(v_{p+1})\) is defined as the smallest
color not assigned to any neighbor of \(v_{p+1}\) belonging to the set \(\{v_1, v_2,\cdots, v_p\}\). The coloring
\(c\) so produced is then a Grundy
coloring of \(G\). (i.e.), every greedy
coloring is a Grundy coloring. The maximum positive integer \(k\) for which a graph \(G\) has a Grundy \(k\)-coloring is denoted by \(\Gamma(G)\) and is called the Grundy
chromatic number of \(G\) or more
simply the Grundy number of \(G\). If
the Grundy number of a graph \(G\) is
\(k\), then in any Grundy \(k\)-coloring of \(G\) (using the colors \(1, 2,\cdots , k\)), every vertex \(v\) of \(G\) colored \(k\) must be adjacent to a vertex colored
\(i\) for each integer \(i\) with \(1\leq
i \le k\). Thus \(\Delta(G)\geq
deg(v)\geq (k-1)\) and so
\[\label{1}
\Gamma(G)\leq \Delta(G)+1\] for every graph \(G\). Since every Grundy coloring of a graph
\(G\) is a proper coloring, it follows
that, \[\chi(G)\leq \Gamma(G).\]
The Grundy number of a graph was perhaps introduced for the first time by Christen and Selkow [5]. In [6], Erdös et., al. proved that the Grundy number of a graph is in fact the same as ochromatic number of a graph which was defined and studied independently by Simmons [7]. In [8] the authors studied the Grundy number of hypercubes and determined the exact values. From computational point of view, polynomial time algorithms for determining the Grundy number have been given for trees in [9] and for partial k-trees in [10]. In a manuscript [11] the NP-completeness of determining the Grundy number of general graphs has been proved. Therefore, they gave an affirmative answer to the problem \(10.4\) posed in the graph coloring problem book [12] which asks whether determining the Grundy chromatic number of graphs is an NP-complete problem.
All graphs we consider are simple and fnite. A path \(m\) is a trail where all its vertices \(v_0, v_1,\dots,v_k\) are distinct. A closed trail whose origin and internal vertices are distinct is called a \(cycle\). A cycle of length \(k\) is called a \(k\)-cycle.
A simple graph in which each pair of distinct vertices is joined by an edge is called a complete graph and it is denoted by \(K_{n}\).
For any integer \(n\geq 4\), the wheel graph \(W_n\)[13] is the \(n-\)vertex graph obtained by joining a vertex \(u_n\) to each of the \(n-1\) vertices \(\{u_1, u_2,\cdots, u_{n-1}\}\) of the cycle graph \(c_{n-1}\).
Cartesian Product \(G\square H\) of graphs \(G\) and \(H\) is a graph such that the vertex set of \(G\square H\) is the Cartesian Product of \(V\left(G \square H\right)\); Vertices \((g,h)\) and \((g^\prime, h^\prime)\) are adjacent in \(G\square H\) if and only if
\(g\) is adjacent to \(g^\prime\) in \(G\) and \(h=h^\prime\).
\(h\) is adjacent to \(h^\prime\) in \(H\) and \(g=g^\prime\).
Theorem 1. Let \(G\) and \(H\) be a path graph of order \(m\geq 6\) and \(n\geq 5\), then \(\Gamma(G\square H) = 5\).
Proof. Let \(V(G)=\{u_i: 1 \leq i
\leq m\}\) and let \(V(H)=\{v_j: 1 \leq
j \leq n\}\). We define the vertices \(V(G \square H) = \{s_{i,j}: 1\leq i\leq m; 1\leq
j\leq n\}\). By symmentry, we need only consider the cases for
\(m\geq 6\) and \(n\geq 5\).
Let \(\alpha_1=23121\); \(\alpha_2=15232\); \(\alpha_3=24313\); \(\alpha_4=31232\);
\(\alpha_5=24313\); \(\alpha_6=31232\); \(\alpha_7=12121\); \(\alpha_8=21212\).
We define a mapping \(\mu : V(G \square H) \to
\mathbb{N}\) as follows.
For \(m \equiv 0 \mod 6\)
and \(n \equiv 0 \mod 5\).
For \(1 \leq i \leq m; 1 \leq j \leq
n\).
\[\mu\left( s_{i,j}\right) = \alpha_1^{\frac{m}{6}}\alpha_2^{\frac{m}{6}}\alpha_3^{\frac{m}{6}}\alpha_4^{\frac{m}{6}}\alpha_5^{\frac{m}{6}}\alpha_6^{\frac{m}{6}}\]
For \(m \equiv 1 \mod 6\)
and \(n \equiv 1 \mod 5\).
The color patern as follows case(1) for \(1
\leq i \leq m-1; 1 \leq j \leq n-1\).
\(\mu\left( s_{m,2j-1}\right) = 1, 1 \leq j
\leq \frac{n}{2}\);
\(\mu\left( s_{m,2j}\right) = 2, 1 \leq j \leq
\frac{n}{2}\);
\(\mu\left( s_{2i-1,n}\right) = 2, 1 \leq i
\leq \frac{m+1}{2}\);
\(\mu\left( s_{m,2j}\right) = 1, 1 \leq i \leq
\frac{m-1}{2}\).
For \(m \equiv 2 \mod 6\)
and \(n \equiv 2 \mod 5\).
The color patern as follows case(2) for \(1
\leq i \leq m-1; 1 \leq j \leq n-1\).
\(\mu\left( s_{m,2j-1}\right) = 2, 1 \leq j
\leq \frac{n+1}{2}\);
\(\mu\left( s_{m,2j}\right) = 1, 1 \leq j \leq
\frac{n-1}{2}\);
\(\mu\left( s_{2i-1,n}\right) = 2, 1 \leq i
\leq \frac{m-1}{2}\);
\(\mu\left( s_{m,2j}\right) = 1, 1 \leq i \leq
\frac{m+1}{2}\).
For \(m \equiv 3 \mod 6\)
and \(n \equiv 3 \mod 5\).
The color patern as follows case(3) for \(1
\leq i \leq m-1; 1 \leq j \leq n-1\).
\(\mu\left( s_{m,2j-1}\right) = 1, 1 \leq j
\leq \frac{n}{2}\);
\(\mu\left( s_{m,2j}\right) = 2, 1 \leq j \leq
\frac{n}{2}\);
\(\mu\left( s_{2i-1,n}\right) = 2, 1 \leq i
\leq \frac{m+1}{2}\);
\(\mu\left( s_{m,2j}\right) = 1, 1 \leq i \leq
\frac{m-1}{2}\).
For \(m \equiv 4 \mod 6\)
and \(n \equiv 4 \mod 5\).
The color patern as follows case(4) for \(1
\leq i \leq m-1; 1 \leq j \leq n-1\).
\(\mu\left( s_{m,2j-1}\right) = 2, 1 \leq j
\leq \frac{n+1}{2}\);
\(\mu\left( s_{m,2j}\right) = 1, 1 \leq j \leq
\frac{n-1}{2}\);
\(\mu\left( s_{2i-1,n}\right) = 2, 1 \leq i
\leq \frac{m-1}{2}\);
\(\mu\left( s_{m,2j}\right) = 1, 1 \leq i \leq
\frac{m+1}{2}\).
For \(m \equiv 5 \mod 6\)
and \(n \equiv 0 \mod 5\).
The color patern as follows case(5) for \(1
\leq i \leq m-1\) and using the color patern as follows case(1)
for \(n \equiv 0 \mod 5\).
\(\mu\left( s_{m,2j-1}\right) = 1, 1 \leq j
\leq \frac{n}{2}\);
\(\mu\left( s_{m,2j}\right) = 2, 1 \leq j \leq
\frac{n}{2}\).
Hence \(\Gamma (G \square H) \leq 5\). Assume that \(\Gamma (G \square H) > 5\). By equation (1), we have \(\Gamma(G)\leq \Delta(G) + 1\). Since \(\Gamma (G \square H)\geq 5\). Therefore \(\Gamma (G \square H)= 5\).
Theorem 2. Let \(G\) and \(H\) be a complete graph of order \(m\geq 3\) and \(n\geq 3\), then \(\Gamma(G\square H) = m+n-2\).
Proof. Let \(V(G)=\{u_i: 1 \leq i \leq m\}\) and let \(V(H)=\{v_j: 1 \leq j \leq n\}\). We define the vertices \(V(G \square H) = \{s_{i,j}: 1\leq i\leq m; 1\leq j\leq n\}\). We define a mapping \(\mu: V(G \square H) \rightarrow N\) as follows: \[\begin{aligned} \mu\left( s_{1,j}\right) &=& j+m-1, \quad\quad 1\leq j\leq n;\\ \mu\left( s_{i,n}\right) &=& i+m-2, \quad\quad 2\leq i\leq m; \\ \mu\left( s_{i,j}\right) &=&\left\{\begin{array}{ll} \text{For} \quad 2\leq i\leq m, \quad 1\leq j\leq n-1\\ i+j-2 \mod m-1, \ \ \text{ if } \ i+j-2 \not\equiv 0 \mod m-1\\ m-1 \mod m-1, \ \ \text{ if } \ i+j-2 \equiv 0 \mod m-1. \end{array}\right. \end{aligned}\]
Hence \(\Gamma (G \square H) \leq m+n-1\). Assume that \(\Gamma (G \square H) > m+n-1\). By equation (1), we have \(\Gamma(G)\leq \Delta(G) + 1\). Since \(\Gamma (G \square H)\geq m+n-1\). Therefore \(\Gamma (G \square H)= m+n-1\).
Theorem 3. Let \(G\) and \(H\) be a cycle graph of order \(m\geq 3\) and \(n\geq 3\), then \(\Gamma(G\square H) = 5\).
Proof. Let \(V(G)=\{u_i: 1 \leq i \leq m\}\) and let \(V(H)=\{v_j: 1 \leq j \leq n\}\). We define the vertices \(V(G \square H) = \{s_{i,j}: 1\leq i\leq m; 1\leq j\leq n\}\). We define a mapping \(\mu: V(G \square H) \rightarrow N\) as follows:
For \(m \equiv 0 \mod 3\).
For \(i \equiv 1 \mod 3\). \[\begin{aligned} \mu\left( s_{i,j}\right) &=\left\{ \begin{array}{ll} \text{For} \quad 1\leq j\leq n-1, \\ 5, \ \ \text{ if } \ j \equiv 1 \mod 3\\ 4, \ \ \text{ if } \ j \equiv 2 \mod 3\\ 3, \ \ \text{ if } \ j \equiv 0 \mod 3\\ \end{array}\right. \end{aligned}\]
For \(i \equiv 2 \mod
3\).
\[\begin{aligned}
\mu\left( s_{i,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 1\leq j\leq n, \\
2, \ \ \text{ if } \ j \equiv 1 \mod 2\\
1, \ \ \text{ if } \ j \equiv 0 \mod 2\\
\end{array}\right.
\end{aligned}\]
For \(i \equiv 0 \mod
3\).
\[\begin{aligned}
\mu\left( s_{i,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 1\leq j\leq n, \\
1, \ \ \text{ if } \ j \equiv 1 \mod 2\\
2, \ \ \text{ if } \ j \equiv 0 \mod 2\\
\end{array}\right.
\end{aligned}\]
For \(m \equiv 1 \mod
3\).
The color patern as follows Case(1) for \(1
\leq i \leq m-4\) and \(1 \leq j \leq
n-4\).
\[\begin{aligned}
\mu\left( s_{m-3,j}\right) = \mu\left( s_{m-1,j}\right)
&=\left\{
\begin{array}{ll}
\text{For} \quad 1\leq j\leq n, \\
2, \ \ \text{ if } \ j \equiv 1 \mod 2\\
1, \ \ \text{ if } \ j \equiv 0 \mod 2\\
\end{array}\right.
\end{aligned}\] \[\begin{aligned}
\mu\left( s_{m-2,j}\right) = \mu\left( s_{m,j}\right)
&=\left\{
\begin{array}{ll}
\text{For} \quad 1\leq j\leq n, \\
1, \ \ \text{ if } \ j \equiv 1 \mod 2\\
2, \ \ \text{ if } \ j \equiv 0 \mod 2\\
\end{array}\right.
\end{aligned}\]
\[\begin{aligned} \mu\left( s_{i,n-3}\right) = \mu\left( s_{i,n-1}\right) &=\left\{ \begin{array}{ll} \text{For} \quad 1\leq j\leq n, \\ 4, \ \ \text{ if } \ i \equiv 1 \mod 3\\ 1, \ \ \text{ if } \ i \equiv 2 \mod 3\\ 2, \ \ \text{ if } \ i \equiv 0 \mod 3\\ \end{array}\right. \end{aligned}\] \[\begin{aligned} \mu\left( s_{i,n-2}\right) = \mu\left( s_{i,n}\right) &=\left\{ \begin{array}{ll} \text{For} \quad 1\leq j\leq n, \\ 5, \ \ \text{ if } \ i \equiv 1 \mod 3\\ 2, \ \ \text{ if } \ i \equiv 2 \mod 3\\ 1, \ \ \text{ if } \ i \equiv 0 \mod 3\\ \end{array}\right. \end{aligned}\]
For \(m \equiv 2 \mod
3\).
The color patern as follows Case(1) for \(1
\leq i \leq m-2\) and \(1 \leq j \leq
n-2\).
\[\begin{aligned}
\mu\left( s_{m-1,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 1\leq j\leq n, \\
2, \ \ \text{ if } \ j \equiv 1 \mod 2\\
1, \ \ \text{ if } \ j \equiv 0 \mod 2\\
\end{array}\right.
\end{aligned}\] \[\begin{aligned}
\mu\left( s_{m,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 1\leq j\leq n, \\
1, \ \ \text{ if } \ j \equiv 1 \mod 2\\
2, \ \ \text{ if } \ j \equiv 0 \mod 2\\
\end{array}\right.
\end{aligned}\]
Hence \(\Gamma (G \square H) \leq 5\). Assume that \(\Gamma (G \square H) > 5\). By equation (1), we have \(\Gamma(G)\leq \Delta(G) + 1\). Since \(\Gamma (G \square H)\geq 5\). Therefore \(\Gamma (G \square H)= 5\).
Theorem 4. Let \(G\) and \(H\) be a wheel graph of order \(m\geq 4\) and \(n\geq 4\), then \(\Gamma(G\square H) = 7\).
Proof. Let \(V(G)=\{u_i: 1 \leq i \leq m-1\}\cup \{u_m\}\) and let \(V(H)=\{v_j: 1 \leq j \leq n-1\}\cup \{v_n\}\), where \(u_m\) and \(v_n\) are are adjacen to \(u_i(1\leq i\leq m-1)\) and \(v_j(1\leq j\leq n-1)\). We define the vertices \(V(G \square H) = \{s_{i,j}: 1\leq i\leq m; 1\leq j\leq n\}\). We define a mapping \(\mu: V(G \square H) \rightarrow N\) as follows:
For \(m \equiv 1 \mod 3\).
For \(n \equiv 1 \mod
3\).
\(\mu\left( s_{m,n}\right) = 7\), \[\begin{aligned}
\mu\left( s_{1,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 1\leq j\leq n-1, \\
6 \ \ \text{ if } \ j \equiv 1 \mod 3\\
5 \ \ \text{ if } \ j \equiv 2 \mod 3\\
4 \ \ \text{ if } \ j \equiv 0 \mod 3\\
\end{array}\right.
\end{aligned}\]
For \(n-1 \equiv 1 \mod
2\).
\[\begin{aligned}
\mu\left( s_{i,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 2\leq i\leq m-1, \\
1 \ \ \text{ if } \ i \equiv 2 \mod 3\\
3 \ \ \text{ if } \ i \equiv 0 \mod 3\\
2 \ \ \text{ if } \ i \equiv 1 \mod 3\\
\end{array}\right.
\end{aligned}\]
For \(n-1 \equiv 0 \mod
2\).
\[\begin{aligned}
\mu\left( s_{i,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 2\leq i\leq m-1, \\
2 \ \ \text{ if } \ i \equiv 2 \mod 3\\
1 \ \ \text{ if } \ i \equiv 0 \mod 3\\
3 \ \ \text{ if } \ i \equiv 1 \mod 3\\
\end{array}\right.
\end{aligned}\] \[\begin{aligned}
\mu\left( s_{i,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 2\leq i\leq m-1, \\
3 \ \ \text{ if } \ i \equiv 0 \mod 3\\
2 \ \ \text{ if } \ i \equiv 1 \mod 3\\
1 \ \ \text{ if } \ i \equiv 2 \mod 3\\
\end{array}\right.
\end{aligned}\]
For \(n \equiv 2 \mod
3\).
The color patern as follows Subcase(1) for \(1
\leq j \leq n-5\).
\(\mu\left( s_{1,n-4}\right) = \mu\left(
s_{1,n-2}\right) = 5\),
\(\mu\left( s_{1,n-3}\right) = \mu\left(
s_{1,n-1}\right) = 4\).
For \(n \equiv 0 \mod
3\).
The color patern as follows Subcase(1) for \(1
\leq j \leq n-3\).
\(\mu\left( s_{1,n-2}\right) = 5\);
\(\mu\left( s_{1,n-1}\right) =
4\).
For \(m \equiv 2 \mod 3\).
The color patern as follows Case(1) for \(1
\leq i \leq m-1\).
\(\mu\left( s_{m-1,n}\right) = 2\).
\[\begin{aligned}
\mu\left( s_{m-1,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 1\leq j\leq n-1, \\
3 \ \ \text{ if } \ j \equiv 1 \mod 2\\
1 \ \ \text{ if } \ j \equiv 0 \mod 2\\
\end{array}\right.
\end{aligned}\]
For \(m \equiv 0 \mod 3\).
The color patern as follows Case(1) for \(1
\leq i \leq m-3\).
\(\mu\left( s_{m-2,n}\right) = 3\);
\(\mu\left( s_{m-1,n}\right) = 2\).
\[\begin{aligned}
\mu\left( s_{m-2,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 1\leq j\leq n-1, \\
1 \ \ \text{ if } \ j \equiv 1 \mod 2\\
2 \ \ \text{ if } \ j \equiv 0 \mod 2\\
\end{array}\right.
\end{aligned}\] \[\begin{aligned}
\mu\left( s_{m-1,j}\right) &=\left\{
\begin{array}{ll}
\text{For} \quad 1\leq j\leq n-1, \\
3 \ \ \text{ if } \ j \equiv 1 \mod 2\\
1 \ \ \text{ if } \ j \equiv 0 \mod 2\\
\end{array}\right.
\end{aligned}\]
Hence \(\Gamma (G\square H) \leq 7\). Assume that \(\Gamma (G\square H) > 7\). Let the color \(1, 2, 3, 4, 5, 6, 7\) and \(8\) be the distinct colors. Suppose we assign the color \(8\) to the vertex \(s_{m,n}\). Now we assigned the colors \(1, 2, 3, 4, 5, 6, 7\) to the neighbourhood vertices of received the color \(8\). Here either every two colors \(x\) and \(y\) with \(x\nleq y\) or every vertex colored \(y\) has not a neighbor colored \(x\). it contradicts by the grundy chromatic number. Since \(\Gamma (G\square H)\geq 7\). Therefore \(\Gamma (G\square H)= 7\).
Theorem 5. Let \(G\) and \(H\) be a star graph of order \(m\geq 3\) and \(n\geq 3\), then \(\Gamma(G\square H) = 4\).
Proof. Let \(V(G)=\{u_i: 1 \leq i \leq m\}\cup \{u_0\}\) and let \(V(H)=\{v_j: 1 \leq j \leq n\}\cup \{v_0\}\), wher \(u_0\) and \(v_0\) are are adjacen to \(u_i(1\leq i\leq m)\) and \(v_j(1\leq j\leq n)\). We define the vertices \(V(G \square H) = \{s_{i,j}: 0\leq i\leq m; 0\leq j\leq n\}\). We define a mapping \(\mu: V(G \square H) \rightarrow N\) as follows: Let \(V(G)=\{u_i: 1 \leq i \leq m\}\) and let \(V(H)=\{v_j: 1 \leq j \leq n\}\). We define the vertices \(V(G \square H) = \{s_{i,j}: 1\leq i\leq m; 1\leq j\leq n\}\). We define a mapping \(\mu: V(G \square H) \rightarrow N\) as follows: \[\begin{aligned} \mu\left( s_{0,0}\right) &= 4,\\ \mu\left( s_{0,j}\right) &= 3, \quad 1\leq j\leq n; \\ \mu\left( s_{i,0}\right) &=\left\{\begin{array}{ll} \text{For} \quad 1\leq i\leq m,\\ 2, \ \ \text{ if } \ i\equiv 1 \mod 2\\ 1, \ \ \text{ if } \ i \equiv 0 \mod 2. \end{array}\right.\\ \mu\left( s_{i,j}\right) &=\left\{\begin{array}{ll} \text{For} \quad 1\leq j\leq n,\\ 1, \ \ \text{ if } \ i\equiv 1 \mod 2\\ 2, \ \ \text{ if } \ i \equiv 0 \mod 2. \end{array}\right. \end{aligned}\] Hence \(\Gamma (G\square H) \leq 4\). Assume that \(\Gamma (G\square H) > 4\). Let the color \(1, 2, 3, 4\) and \(5\) be the distinct colors. Suppose we assign the color \(5\) to the vertex \(s_{0,0}\). Now we assigned the colors \(1, 2, 3, 4\) to the neighbourhood vertices of received the color \(5\). Here either every two colors \(x\) and \(y\) with \(x\nleq y\) or every vertex colored \(y\) has not a neighbor colored \(x\). it contradicts by the grundy chromatic number. Since \(\Gamma (G\square H)\geq 4\). Therefore \(\Gamma (G\square H)= 4\).
In this paper, we have demonstrated the new results on Grundy chromatic number of Cartesian Product of path graph, complete graph, cycle graph, complete graph, wheel graph and star graph. Furthermore, we extend our work to generalized Grundy chromatic number of some other product of graphs.
The authors declare no conflict of interests.