Results on Grundy Chromatic Number of Join Graph of Graphs

R, Stella

doi:10.61091/ars157-06

Abstract

1. Introduction
2. Preliminaries
3. Main Results
4. Conclusion
Conflict of Interest

References

Ars Combinatoria

Volume 157
Pages: 65-71

Research article

Results on Grundy Chromatic Number of Join Graph of Graphs

^¹, ^²

¹Department of Mathematics, Queen Mary’s College, Chennai-600 004, Tamil Nadu, India.

²Department of Mathematics, Presidency College, Chennai-600005, Tamil Nadu, India.

Received: 26/07/2023
Accepted: 07/12/2023
Published: 13/12/2023

Copyright Link
License

Abstract

A Grundy $k$ -coloring of a graph $G$ is a proper $k$ -coloring of vertices in $G$ using colors ${1, 2, \dots, 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 $Γ (G)$ , is the largest integer $k$ , such that there exists a Grundy $k$ -coloring for $G$ . It can be easily seen that $Γ (G)$ 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.

Keywords: Graph coloring, Chromatic number, Grundy coloring, Grundy chromatic number

1. Introduction

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 \leq 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 $ϕ : v_{1}, v_{2}, \dots, 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}, \dots, v_{p}$ for some integer $p$ with $1 \leq p \leq 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}, \dots, 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 $Γ (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, \dots, k$ ), every vertex $v$ of $G$ colored $k$ must be adjacent to a vertex colored $i$ for each integer $i$ with $1 \leq i \leq k$ . Thus $Δ (G) \geq d e g (v) \geq (k - 1)$ and so
$Γ (G) \leq Δ (G) + 1$ for every graph $G$ . Since every Grundy coloring of a graph $G$ is a proper coloring, it follows that, $χ (G) \leq Γ (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.

2. Preliminaries

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 $c y c l e$ . 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}, \dots, u_{n - 1}}$ of the cycle graph $c_{n - 1}$ .

Cartesian Product $G H$ of graphs $G$ and $H$ is a graph such that the vertex set of $G H$ is the Cartesian Product of $V (G H)$ ; Vertices $(g, h)$ and $(g^{'}, h^{'})$ are adjacent in $G H$ if and only if

$g$ is adjacent to $g^{'}$ in $G$ and $h = h^{'}$ .
$h$ is adjacent to $h^{'}$ in $H$ and $g = g^{'}$ .

3. Main Results

Theorem 1. Let $G$ and $H$ be a path graph of order $m \geq 6$ and $n \geq 5$ , then $Γ (G 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 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 $α_{1} = 23121$ ; $α_{2} = 15232$ ; $α_{3} = 24313$ ; $α_{4} = 31232$ ;
$α_{5} = 24313$ ; $α_{6} = 31232$ ; $α_{7} = 12121$ ; $α_{8} = 21212$ .
We define a mapping $μ : V (G H) \to N$ as follows.

Case (1):

For $m \equiv 0 \mod 6$ and $n \equiv 0 \mod 5$ .
For $1 \leq i \leq m; 1 \leq j \leq n$ .

$μ (s_{i, j}) = α_{1}^{\frac{m}{6}} α_{2}^{\frac{m}{6}} α_{3}^{\frac{m}{6}} α_{4}^{\frac{m}{6}} α_{5}^{\frac{m}{6}} α_{6}^{\frac{m}{6}}$

Case (2):

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$ .
$μ (s_{m, 2 j - 1}) = 1, 1 \leq j \leq \frac{n}{2}$ ;
$μ (s_{m, 2 j}) = 2, 1 \leq j \leq \frac{n}{2}$ ;
$μ (s_{2 i - 1, n}) = 2, 1 \leq i \leq \frac{m + 1}{2}$ ;
$μ (s_{m, 2 j}) = 1, 1 \leq i \leq \frac{m - 1}{2}$ .

Case (3):

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$ .
$μ (s_{m, 2 j - 1}) = 2, 1 \leq j \leq \frac{n + 1}{2}$ ;
$μ (s_{m, 2 j}) = 1, 1 \leq j \leq \frac{n - 1}{2}$ ;
$μ (s_{2 i - 1, n}) = 2, 1 \leq i \leq \frac{m - 1}{2}$ ;
$μ (s_{m, 2 j}) = 1, 1 \leq i \leq \frac{m + 1}{2}$ .

Case (4):

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$ .
$μ (s_{m, 2 j - 1}) = 1, 1 \leq j \leq \frac{n}{2}$ ;
$μ (s_{m, 2 j}) = 2, 1 \leq j \leq \frac{n}{2}$ ;
$μ (s_{2 i - 1, n}) = 2, 1 \leq i \leq \frac{m + 1}{2}$ ;
$μ (s_{m, 2 j}) = 1, 1 \leq i \leq \frac{m - 1}{2}$ .

Case (5):

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$ .
$μ (s_{m, 2 j - 1}) = 2, 1 \leq j \leq \frac{n + 1}{2}$ ;
$μ (s_{m, 2 j}) = 1, 1 \leq j \leq \frac{n - 1}{2}$ ;
$μ (s_{2 i - 1, n}) = 2, 1 \leq i \leq \frac{m - 1}{2}$ ;
$μ (s_{m, 2 j}) = 1, 1 \leq i \leq \frac{m + 1}{2}$ .

Case (6):

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$ .
$μ (s_{m, 2 j - 1}) = 1, 1 \leq j \leq \frac{n}{2}$ ;
$μ (s_{m, 2 j}) = 2, 1 \leq j \leq \frac{n}{2}$ .

Hence $Γ (G H) \leq 5$ . Assume that $Γ (G H) > 5$ . By equation (1), we have $Γ (G) \leq Δ (G) + 1$ . Since $Γ (G H) \geq 5$ . Therefore $Γ (G H) = 5$ .

Theorem 2. Let $G$ and $H$ be a complete graph of order $m \geq 3$ and $n \geq 3$ , then $Γ (G 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 H) = {s_{i, j} : 1 \leq i \leq m; 1 \leq j \leq n}$ . We define a mapping $μ : V (G H) \to N$ as follows: $\begin{aligned} μ (s_{1, j}) & = & j + m - 1, 1 \leq j \leq n; \\ μ (s_{i, n}) & = & i + m - 2, 2 \leq i \leq m; \\ μ (s_{i, j}) & = & {\begin{cases} For 2 \leq i \leq m, 1 \leq j \leq n - 1 \\ i + j - 2 \mod m - 1, if i + j - 2 ≢ 0 \mod m - 1 \\ m - 1 \mod m - 1, if i + j - 2 \equiv 0 \mod m - 1. \end{cases} \end{aligned}$

Hence $Γ (G H) \leq m + n - 1$ . Assume that $Γ (G H) > m + n - 1$ . By equation (1), we have $Γ (G) \leq Δ (G) + 1$ . Since $Γ (G H) \geq m + n - 1$ . Therefore $Γ (G H) = m + n - 1$ .

Theorem 3. Let $G$ and $H$ be a cycle graph of order $m \geq 3$ and $n \geq 3$ , then $Γ (G H) = 5$ .

Case (1):

For $m \equiv 0 \mod 3$ .

Subcase (1):: For $i \equiv 1 \mod 3$ . $\begin{aligned} μ (s_{i, j}) & = {\begin{cases} For 1 \leq j \leq n - 1, \\ 5, if j \equiv 1 \mod 3 \\ 4, if j \equiv 2 \mod 3 \\ 3, if j \equiv 0 \mod 3 \end{cases} \end{aligned}$
Subcase (2):: For $i \equiv 2 \mod 3$ .
$\begin{aligned} μ (s_{i, j}) & = {\begin{cases} For 1 \leq j \leq n, \\ 2, if j \equiv 1 \mod 2 \\ 1, if j \equiv 0 \mod 2 \end{cases} \end{aligned}$
Subcase (3):: For $i \equiv 0 \mod 3$ .
$\begin{aligned} μ (s_{i, j}) & = {\begin{cases} For 1 \leq j \leq n, \\ 1, if j \equiv 1 \mod 2 \\ 2, if j \equiv 0 \mod 2 \end{cases} \end{aligned}$

Case (2):

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} μ (s_{m - 3, j}) = μ (s_{m - 1, j}) & = {\begin{cases} For 1 \leq j \leq n, \\ 2, if j \equiv 1 \mod 2 \\ 1, if j \equiv 0 \mod 2 \end{cases} \end{aligned}$ $\begin{aligned} μ (s_{m - 2, j}) = μ (s_{m, j}) & = {\begin{cases} For 1 \leq j \leq n, \\ 1, if j \equiv 1 \mod 2 \\ 2, if j \equiv 0 \mod 2 \end{cases} \end{aligned}$

$\begin{aligned} μ (s_{i, n - 3}) = μ (s_{i, n - 1}) & = {\begin{cases} For 1 \leq j \leq n, \\ 4, if i \equiv 1 \mod 3 \\ 1, if i \equiv 2 \mod 3 \\ 2, if i \equiv 0 \mod 3 \end{cases} \end{aligned}$ $\begin{aligned} μ (s_{i, n - 2}) = μ (s_{i, n}) & = {\begin{cases} For 1 \leq j \leq n, \\ 5, if i \equiv 1 \mod 3 \\ 2, if i \equiv 2 \mod 3 \\ 1, if i \equiv 0 \mod 3 \end{cases} \end{aligned}$

Case (3):

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} μ (s_{m - 1, j}) & = {\begin{cases} For 1 \leq j \leq n, \\ 2, if j \equiv 1 \mod 2 \\ 1, if j \equiv 0 \mod 2 \end{cases} \end{aligned}$ $\begin{aligned} μ (s_{m, j}) & = {\begin{cases} For 1 \leq j \leq n, \\ 1, if j \equiv 1 \mod 2 \\ 2, if j \equiv 0 \mod 2 \end{cases} \end{aligned}$

Hence $Γ (G H) \leq 5$ . Assume that $Γ (G H) > 5$ . By equation (1), we have $Γ (G) \leq Δ (G) + 1$ . Since $Γ (G H) \geq 5$ . Therefore $Γ (G H) = 5$ .

Theorem 4. Let $G$ and $H$ be a wheel graph of order $m \geq 4$ and $n \geq 4$ , then $Γ (G 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 H) = {s_{i, j} : 1 \leq i \leq m; 1 \leq j \leq n}$ . We define a mapping $μ : V (G H) \to N$ as follows:

Case (1):

For $m \equiv 1 \mod 3$ .

Subcase (1):

For $n \equiv 1 \mod 3$ .
$μ (s_{m, n}) = 7$ , $\begin{aligned} μ (s_{1, j}) & = {\begin{cases} For 1 \leq j \leq n - 1, \\ 6 if j \equiv 1 \mod 3 \\ 5 if j \equiv 2 \mod 3 \\ 4 if j \equiv 0 \mod 3 \end{cases} \end{aligned}$

For $n - 1 \equiv 1 \mod 2$ .
$\begin{aligned} μ (s_{i, j}) & = {\begin{cases} For 2 \leq i \leq m - 1, \\ 1 if i \equiv 2 \mod 3 \\ 3 if i \equiv 0 \mod 3 \\ 2 if i \equiv 1 \mod 3 \end{cases} \end{aligned}$
For $n - 1 \equiv 0 \mod 2$ .
$\begin{aligned} μ (s_{i, j}) & = {\begin{cases} For 2 \leq i \leq m - 1, \\ 2 if i \equiv 2 \mod 3 \\ 1 if i \equiv 0 \mod 3 \\ 3 if i \equiv 1 \mod 3 \end{cases} \end{aligned}$ $\begin{aligned} μ (s_{i, j}) & = {\begin{cases} For 2 \leq i \leq m - 1, \\ 3 if i \equiv 0 \mod 3 \\ 2 if i \equiv 1 \mod 3 \\ 1 if i \equiv 2 \mod 3 \end{cases} \end{aligned}$

Subcase (2):

For $n \equiv 2 \mod 3$ .
The color patern as follows Subcase(1) for $1 \leq j \leq n - 5$ .
$μ (s_{1, n - 4}) = μ (s_{1, n - 2}) = 5$ ,
$μ (s_{1, n - 3}) = μ (s_{1, n - 1}) = 4$ .

Subcase (2):

For $n \equiv 0 \mod 3$ .
The color patern as follows Subcase(1) for $1 \leq j \leq n - 3$ .
$μ (s_{1, n - 2}) = 5$ ; $μ (s_{1, n - 1}) = 4$ .

Case (2):

For $m \equiv 2 \mod 3$ . The color patern as follows Case(1) for $1 \leq i \leq m - 1$ .
$μ (s_{m - 1, n}) = 2$ . $\begin{aligned} μ (s_{m - 1, j}) & = {\begin{cases} For 1 \leq j \leq n - 1, \\ 3 if j \equiv 1 \mod 2 \\ 1 if j \equiv 0 \mod 2 \end{cases} \end{aligned}$

Case (3):

For $m \equiv 0 \mod 3$ . The color patern as follows Case(1) for $1 \leq i \leq m - 3$ .
$μ (s_{m - 2, n}) = 3$ ; $μ (s_{m - 1, n}) = 2$ . $\begin{aligned} μ (s_{m - 2, j}) & = {\begin{cases} For 1 \leq j \leq n - 1, \\ 1 if j \equiv 1 \mod 2 \\ 2 if j \equiv 0 \mod 2 \end{cases} \end{aligned}$ $\begin{aligned} μ (s_{m - 1, j}) & = {\begin{cases} For 1 \leq j \leq n - 1, \\ 3 if j \equiv 1 \mod 2 \\ 1 if j \equiv 0 \mod 2 \end{cases} \end{aligned}$

Hence $Γ (G H) \leq 7$ . Assume that $Γ (G 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 ≰ y$ or every vertex colored $y$ has not a neighbor colored $x$ . it contradicts by the grundy chromatic number. Since $Γ (G H) \geq 7$ . Therefore $Γ (G H) = 7$ .

Theorem 5. Let $G$ and $H$ be a star graph of order $m \geq 3$ and $n \geq 3$ , then $Γ (G 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 H) = {s_{i, j} : 0 \leq i \leq m; 0 \leq j \leq n}$ . We define a mapping $μ : V (G H) \to 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 H) = {s_{i, j} : 1 \leq i \leq m; 1 \leq j \leq n}$ . We define a mapping $μ : V (G H) \to N$ as follows: $\begin{aligned} μ (s_{0, 0}) & = 4, \\ μ (s_{0, j}) & = 3, 1 \leq j \leq n; \\ μ (s_{i, 0}) & = {\begin{cases} For 1 \leq i \leq m, \\ 2, if i \equiv 1 \mod 2 \\ 1, if i \equiv 0 \mod 2. \end{cases} \\ μ (s_{i, j}) & = {\begin{cases} For 1 \leq j \leq n, \\ 1, if i \equiv 1 \mod 2 \\ 2, if i \equiv 0 \mod 2. \end{cases} \end{aligned}$ Hence $Γ (G H) \leq 4$ . Assume that $Γ (G 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 ≰ y$ or every vertex colored $y$ has not a neighbor colored $x$ . it contradicts by the grundy chromatic number. Since $Γ (G H) \geq 4$ . Therefore $Γ (G H) = 4$ .

4. Conclusion

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.

Conflict of Interest

The authors declare no conflict of interests.

References:

Füredi, Z., Gyárfás, A., Sárközy, G. N., & Selkow, S., (2008). Inequalities for the first-fit chromatic number. Journal of Graph Theory, 59(1), pp.75-88.[Google Scholor]
Gyárfás, A. and Lehel, J., 1988. On-line and first fit colorings of graphs. Journal of Graph theory, 12(2), pp.217-227.[Google Scholor]
Zaker, M., 2005. Grundy chromatic number of the complement of bipartite graphs. The Australasian Journal of Combinatorics, 31, pp.325-330.[Google Scholor]
Caro, Y., Sebo, A. and Tarsi, M., 1996. Recognizing greedy structures. Journal of Algorithms, 20(1), pp.137-156.[Google Scholor]
Christen, C.A. and Selkow, S.M., 1979. Some perfect coloring properties of graphs. Journal of Combinatorial Theory, Series B, 27(1), pp.49-59.[Google Scholor]
Erdös, P., Hare, W.R., Hedetniemi, S.T. and Laskar, R.C., 1987. On the equality of the Grundy and ochromatic numbers of a graph. Journal of Graph Theory, 11(2), pp.157-159.[Google Scholor]
Sopena, E., 1997. The chromatic number of oriented graphs. Journal of Graph Theory, 25(3), pp.191-205.[Google Scholor]
Hoffman, D.G. and Johnson Jr, P.D., 1999. Greedy colorings and the Grundy chromatic number of the n-cube. Bulletin of the Institute of Combinatorics and its Applications, 26, pp.49-57.[Google Scholor]
Hedetniemi, S.M., Hedetniemi, S.T. and Beyer, T., 1982. A linear algorithm for the Grundy (coloring) number of a tree. Congressus Numerantium 36, pp.351-363.[Google Scholor]
Telle, J.A. and Proskurowski, A., 1997. Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics, 10(4), pp.529-550.[Google Scholor]
Goyal, N. and Vishwanathan, S., 1997. NP-completeness of undirected Grundy numbering and related problems. Manuscript, Bombay.[Google Scholor]
Jensen, T.R. and Toft, B., 2011. Graph coloring problems. John Wiley & Sons.[Google Scholor]
Vernold, J. and Kaliraj, K., 2016. On equitable coloring of corona of wheels. Electronic Journal of Graph Theory and Applications, 4(2), pp.206-222.[Google Scholor]

[1] Füredi, Z., Gyárfás, A., Sárközy, G. N., & Selkow, S., (2008). Inequalities for the first-fit chromatic number. Journal of Graph Theory, 59(1), pp.75-88.[Google Scholor]

[1] Gyárfás, A. and Lehel, J., 1988. On-line and first fit colorings of graphs. Journal of Graph theory, 12(2), pp.217-227.[Google Scholor]

[1] Zaker, M., 2005. Grundy chromatic number of the complement of bipartite graphs. The Australasian Journal of Combinatorics, 31, pp.325-330.[Google Scholor]

[1] Caro, Y., Sebo, A. and Tarsi, M., 1996. Recognizing greedy structures. Journal of Algorithms, 20(1), pp.137-156.[Google Scholor]

[1] Christen, C.A. and Selkow, S.M., 1979. Some perfect coloring properties of graphs. Journal of Combinatorial Theory, Series B, 27(1), pp.49-59.[Google Scholor]

[1] Erdös, P., Hare, W.R., Hedetniemi, S.T. and Laskar, R.C., 1987. On the equality of the Grundy and ochromatic numbers of a graph. Journal of Graph Theory, 11(2), pp.157-159.[Google Scholor]

[1] Sopena, E., 1997. The chromatic number of oriented graphs. Journal of Graph Theory, 25(3), pp.191-205.[Google Scholor]

[1] Hoffman, D.G. and Johnson Jr, P.D., 1999. Greedy colorings and the Grundy chromatic number of the n-cube. Bulletin of the Institute of Combinatorics and its Applications, 26, pp.49-57.[Google Scholor]

[1] Hedetniemi, S.M., Hedetniemi, S.T. and Beyer, T., 1982. A linear algorithm for the Grundy (coloring) number of a tree. Congressus Numerantium 36, pp.351-363.[Google Scholor]

[1] Telle, J.A. and Proskurowski, A., 1997. Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics, 10(4), pp.529-550.[Google Scholor]

[1] Goyal, N. and Vishwanathan, S., 1997. NP-completeness of undirected Grundy numbering and related problems. Manuscript, Bombay.[Google Scholor]

[1] Jensen, T.R. and Toft, B., 2011. Graph coloring problems. John Wiley & Sons.[Google Scholor]

[1] Vernold, J. and Kaliraj, K., 2016. On equitable coloring of corona of wheels. Electronic Journal of Graph Theory and Applications, 4(2), pp.206-222.[Google Scholor]

Contents

Ars Combinatoria

Results on Grundy Chromatic Number of Join Graph of Graphs

Abstract

1. Introduction

2. Preliminaries

3. Main Results

4. Conclusion

Conflict of Interest

References:

Information

Guidelines

CP Initiatives

Follow CP