Solving the dynamic coloring problem for direct products of paths with fan graphs

DOI: 10.2478/auom-2023-0006 An. S¸t. Univ. Ovidius Constant¸a Vol. 31(1),2023,115–142 Solving the dynamic coloring problem for direct products of paths with fan graphs Ra´ul M. Falc´on, S. Gowri and M. Venkatachalam Abstract This paper deals with the r-dynamic chromatic problem of the direct product of a path with a fan graph Fm,n. The problem is completely solved except for the case n<r∈ {2m+ 2,2m+ 3}, which is solved under certain assumptions. It enables us to determine in particular the dynamic chromatic number concerning this problem, for all r≤7, and also, for all m∈ {1,2}. 1 Introduction Let rand `be two positive integers. An r-dynamic proper `-coloring of a finite and simple graph G= (V(G), E(G)) is any map c:V(G)→ {0, . . . , ` −1} such that c(v)6=c(w), for every pair of adjacent vertices v, w ∈V(G), and |c(N(v))| ≥ min {r, d(v)},(1) for every vertex v∈V(G), where N(v) and d(v) denote, respectively, the neighborhood and the degree of the vertex v. The r-dynamic chromatic number of the graph Gis the minimum positive integer ksuch that Ghas an r-dynamic proper k-coloring. It is denoted χr(G). Both concepts were introduced by Montgomery [19] as a natural generalization of the classical problem of graph coloring. More specifically, if r= 1, then these two concepts coincide with the classical ones of proper `-coloring and chromatic number of a graph. Key Words: Dynamic coloring problem, direct product, path, fan graph. 2010 Mathematics Subject Classification: Primary 05C15. Received: 05.01.2022 Accepted: 04.07.2022 115 SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 116 Since the original manuscript of Montgomery, a wide amount of authors have dealt with the problem of determining the r-dynamic chromatic number of distinct types of graphs. As a first stage, they focused on the case r= 2 [2, 3, 5, 6], whereas the case r > 2 has received particular attention in the recent literature [8, 12, 20]. Of special relevance for the aim of this paper is the study of the r-dynamic coloring of different types of products of graphs [1, 4, 16, 17]. Particularly, it has recently been studied the r-dynamic chromatic number of the direct product of paths with paths, cycles, complete graphs, wheel graphs and star graphs [9, 7, 11]. This paper delves into this last topic by focusing on the direct product of a path with a fan graph. Notice that the r-dynamic coloring of fan graphs has already been dealt with [10, 18, 21]. The paper is organized as follows. In Section 2, we describe some preliminary concepts and results on Graph Theory that are used throughout the manuscript. Then, a detailed study of cases is analyzed in Section 3 for solving the r-dynamic coloring problem of the direct product of a path with a fan graph Fm,n. Particularly, this problem is completely solved except for the case n<r∈ {2m+ 2,2m+ 3}, which is solved under certain assumptions. In order to make easier the reading of the manuscript, a series of examples illustrate each case of the study. Finally, Section 4 makes use of the obtained results for establishing the exact solution of the mentioned problem, whenever r≤7 or m∈ {1,2}. 2 Preliminaries This section deals with some preliminary concepts and results on Graph Theory that are used throughout the paper. For more details about this topic, we refer the reader to the classical manuscript of Harary [13]. Any graph G= (V(G), E(G)) is formed by a set of vertices V(G) and a set of edges E(G) so that each edge joins two vertices, which are called adjacent. The number of vertices and edges are, respectively, the order and size of G. If both of them are finite, then the graph is finite. From now on, let vw denote the edge formed by two vertices v, w ∈V(G). If v=w, then the edge is a loop. A graph is simple if it contains no loops and no two edges join the same pair of vertices. All the graphs in this paper are simple and finite. Apath between two distinct vertices v, w ∈V(G) is any ordered sequence of nadjacent vertices hv0=v, v1, . . . , vn−2, vn−1=wiin V(G), with n > 2, such that all the vertices under consideration are pairwise distinct. From here on, let Pndenote the path of order n. Then, the fan graph Fm,n is the graph resulting after joining each one of the vertices of the path Pnwith misolated vertices. If m= 1 (respectively, m= 2), then it constitutes the simple fan graph F1,n (respectively, the double fan graph F2,n). SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 117 The direct product of two finite simple graphs G= (V(G), E(G)) and H= (V(H), E(H)) is the graph G×H, whose set of vertices is the Cartesian product V(G)×V(H), and two such vertices (v, v0) and (w, w0) are adjacent if and only if vw ∈E(G) and v0w0∈E(H). Figure 1 illustrates this concept for the direct product P3×F1,3. Figure 1: Construction of the direct product P3×F1,3. The neighborhood NG(v) of a vertex v∈V(G) is the set formed by its adjacent vertices. Its cardinality is the degree dG(v) of the vertex v. When there is no risk of confusion, the respective notations N(v) and d(v) are used. Let δ(G) and ∆(G) respectively denote the minimum and maximum vertex degree of the graph G. The following result holds readily from the previous definitions. Lemma 1. Let Gand Hbe two finite simple graphs. Then, 1. dG×H((v, w)) = dG(v)dH(w), for all (v, w)∈V(G×H). 2. δ(G×H) = δ(G)δ(H). 3. ∆(G×H) = ∆(G) ∆(H). Concerning the dynamic coloring problem described in the introductory section, the following results are known. Lemma 2. [14] Let Gbe a simple finite graph and let rbe a positive integer. Then, min {r, ∆(G)}+ 1 ≤χr(G)≤χr+1(G). Moreover, χr(G)≤χ∆(G)(G). Lemma 3. [15] Let nand rbe two positive integers such that n > 2. Then, χ1(Pn) = 2, and χr(Pn) = 3, whenever r > 1. SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 118 Lemma 4. [10] Let m,nand rbe three positive integers such that n > 2. Then, χr(Fm,n) =                3,if r∈ {1,2}, 2r−1,if 3≤r≤min{m+ 1, n}, n+r−1,if n<r≤m+ 1, m+r, if max{3, m + 1} ≤ r≤n, m+n, if r≥max{m+ 1, n}. Lemma 5. [9] Let Gand Hbe two finite simple graphs and let rbe a positive integer such that r≤δ(G0), for some G0∈ {G, H}. Then, χr(G×H)≤ χr(G0). 3 Dynamic coloring of Pl×Fm,n Let l > 2, n > 2, mand rbe four positive integers. This section deals with the dynamic coloring problem for the direct product of the path Pl= hu0, . . . , ul−1iand the fan graph Fm,n, where V(Fm,n) = {v0, . . . , vm−1, w0, ...,wn−1}arises from misolated vertices v0, . . . , vm−1and a path hw0,..., wn−1i. From Lemma 1, δ(Pl×Fm,n) = min{m+ 1, n}and ∆(Pl×Fm,n) = max{2m+ 4,2n}. The following study of cases arises. 3.1 Case r≥2m+ 4 Lemma 6. If r≥2m+ 4, then χr(Pl×Fm,n)=2m+ min{2n, r}. Proof. Let cbe an r-dynamic proper χr(Pl×Fm,n)-coloring of Pl×Fm,n. Since d(u1w0)=2m+2 <2m+4 ≤r, Condition (1) applied to the vertex u1w0im- plies that the set {c(u0v0), . . . , c(u0vm−1), c(u2v0), . . . , c(u2vm−1)}is formed by 2mdistinct colors and also that no vertex in {u0w0, . . . , u0wn−1, u2w0, ...,u2wn−1}is colored by one of these colors. Otherwise, one could find a vertex u1wi, with 0 ≤i < n, such that |c(N(u1wi))|< d(uiwi)≤2m+ 4, which would contradict Condition (1). Thus, since d(u1v0)=2n, the same condition applied to the vertex u1v0implies that the set {c(u0w0), . . . , c(u0wn−1), c(u2w0), . . . , c(u2wn−1)}is formed by min{2n, r}extra distinct colors. Hence, 2m+ min{2n, r} ≤ χr(Pl×Fm,n). In order to prove that this lower bound is tight, it is enough to consider the r-dynamic proper coloring cof the direct product Pl×Fm,n such that, for all i<l,j < m and k < n, we have that c(uivj) = min{2n, r}+m·imod 4 2+j and SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 119 c(uiwk) =                2k+imod 4 2mod r, if          r≥2n, r < 2nis odd, r < 2nis even and k6∈ {r 2, . . . , r −1}, 2k+ 1 −imod 4 2mod r, otherwise. Here, it is relevant that r≥6. (Figure 2 illustrates the direct product P4×F2,5, for r∈ {8,9}.) Figure 2: r-dynamic proper (r+ 4)-coloring of the direct product P4×F2,5, for r= 8 (left) and r= 9 (right). 3.2 Case n≥r∈ {2m+ 2,2m+ 3} Proposition 1. Let r∈ {2m+ 2,2m+ 3}be such that r≤n. Then, χr(Pl× Fm,n) = 2m+r. Proof. Let cbe an r-dynamic proper χr(Pl×Fm,n)-coloring of Pl×Fm,n. Condition (1) implies that the 2mvertices in N(u1w0)\ {u0w1, u2w1}are colored with pairwise distinct colors, and also that all of these colors are different from the, at least, rdistinct colors of the set N(u0v0) = {c(u1w0), . . . , c(u1wn−1)}. Thus, the result holds because, from Lemmas 2 and 6, 2m+r≤χr(Pl× Fm,n)≤χ2m+4(Pl×Fm,n)=2m+r. 3.3 Case n<r∈ {2m+ 2,2m+ 3} Lemma 7. Let r∈ {2m+ 2,2m+ 3}be such that n < r. Then, 2m+n≤ χr(Pl×Fm,n). SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 120 Proof. Let cbe an r-dynamic proper χr(Pl×Fm,n)-coloring of Pl×Fm,3. Condition (1) implies that the 2m+ 2 vertices of N(u1w0) are colored by pairwise distinct colors. Similarly, since n < r, the nvertices of N(u0v0) are colored by pairwise distinct colors. From adjacency, these ncolors are different from those ones in c(N(u0v0)\ {u0w1, u2w1}). The next result shows some cases for m= 2 in which the lower bound in Lemma 7 is reached. Proposition 2. Let r∈ {6,7}and n∈ {r−2, r −1}. Then, χr(Pl×F2,n) = n+ 4. Proof. Let us prove each case separately. •Case r= 6 and n∈ {4,5}. From Lemma 7, we have that n+ 4 ≤χr(Pl×F2,n). In order to prove that this lower bound is reached, it is enough to consider the 6-dynamic proper (n+4)-coloring cof the direct product Pl×F2,n that is described so that, for all i < l,j < 2 and k < n, c(uivj) = (4 + 2 + i 2mod 4,if j= 0, 2 + i 2mod 4,if j= 1. c(uiwk) =                        8,if n= 5 and k= 2, 4 + 3 + i 2mod 4,if iis even and k= 0, 4 + 1 + i 2mod 4,if iis odd and k= 0, i 2mod 4,if k= 1, 4 + i 2mod 4,if k=n−2, 3 + i 2mod 4,if iis even and k=n−1, 1 + i 2mod 4,if iis odd and k=n−1. (Figure 3 illustrates the case l= 8.) •Case (n, r) = (5,7). From Lemma 7, we have that 9 ≤χ7(Pl×F2,5). Figure 4 illustrates that this lower bound is tight for all l∈ {3,4,5}. It is also reached for l= 6, as it is illustrated in Figure 5 (left). In order to prove that the mentioned lower bound is also reached for all l≥7, it is enough to consider the 7-dynamic proper 9-coloring cof the direct product Pl×F2,5that is described so that, for all i<l,j < 2 and k < n, SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 121 Figure 3: 6-dynamic proper 8- and 9-colorings of P8×F2,n. c(uivj) =      7,if (i, j) = (0,0), (i+j) mod 9,if (i, j)6∈ {(0,0),(l−1,1)}, (l+ 2) mod 9,if (i, j)=(l−1,1). c(uiwk) =                                            6,if (i, k) = (1,1), i+ 4,if k= 2 and i∈ {0,1}, (l−5) mod 9,if (i, k)=(l−3,4), (l+ 1) mod 9,if (i, k)=(l−2,1), (l−6) mod 9,if (i, k)=(l−2,4), lmod 9,if (i, k)∈ {(l−3,3),(l−2,3)}, (i−2) mod 9,if k= 0, (i+ 4) mod 9,if k= 1 and i6∈ {1, l −2}, (i−3) mod 9,if k∈ {2,3}and (i, k)6∈ {(0,2),(1,2), (l−3,3),(l−2,3)}, (i+ 3) mod 9,if k= 4 and i6∈ {l−3, l −2}. (Figure 5 (right) illustrates the case l= 7.) SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 122 Figure 4: 7-dynamic proper 9-coloring of Pl×F2,5, for l∈ {3,4,5}. Figure 5: 7-dynamic proper 9-coloring of Pl×F2,5, for l∈ {6,7}. •Case (n, r) = (6,7). From Lemma 7, 10 ≤χ7(Pl×F2,6). This lower bound is reached, because of the 7-dynamic proper 10-coloring of Pl×F2,6such that, for all i<l, j < 2 and k < 6, we have that c(uivj) = 3j+ 4 + 1 + i+1 2mod 3 and c(uiwk) =      2k+i 2mod 2,if k∈ {0,1}, 3k−2 + i 2mod 3,if k∈ {2,3}, 2k−8 + 1 + i 2mod 2,if k∈ {4,5}, (Figure 6 illustrates the case l= 8.) SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 123 Figure 6: 7-dynamic proper 10-coloring of P8×F2,6. The next result shows that an extra color is however required for (m, n, r) = (2,4,7). Proposition 3. It is verified that χ7(Pl×F2,4)=9. Proof. Let cbe a 7-dynamic proper χ7(Pl×F2,4)-coloring of Pl×F2,4. From Lemma 7, this map crequires, at least, eight distinct colors. If this lower bound were tight, then Condition (1) implies that both sets {c(u1w0), c(u1w1), c(u1w2), c(u1w3)}and {c(u0w1), c(u0w2), c(u2w1), c(u2w2)}would be formed by the same four pairwise distinct colors. None of these colors coincides with one of the four distinct colors of the set {c(u0v0), c(u0v1), c(u2v0), c(u2v1)}. As a consequence, two distinct colors of this last set would be required for coloring the vertices u1v0and u1v1. But then, |c(N(u1v0)| ≤ 6, which contradicts Condition (1). Hence, 9 ≤χ7(Pl×F2,4). In order to prove that this lower bound is tight, it is enough to define the map cso that, for all i<l, j < 2 and k < 4, we have that c(uivj) = 3 + j+ 2 1 + i+1 2mod 3and c(uiwk) =                3+(imod 6),if k= 0, i 2mod 3,if k= 1, 1 + i+1 2mod 3,if k= 2, 4+(imod 6),if iis even and k= 3, 2+(imod 6),if iis odd and k= 3. (Figure 7 illustrates the case l= 8.) SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 130 Proposition 8. If n<r≤min{2m+ 1,2n}, then χr(Pl×Fm,n) =      2r−1,if r≤m+ 1, r+m, if n<m+ 1 < r, r+n−2,if m+ 1 ≤n < r. Proof. Notice that m > 1. Let us prove each case separately. •Case r≤m+ 1. From Lemma 8, we have that χr(Pl×Fm,n)≥2r−1. In order to prove that this lower bound is tight, it is enough to consider the r-dynamic proper (2r−1)-coloring cof the direct product Pl×Fm,n such that, for all i < l,j < m and k < n, we have that c(uivj) = r+ (jmod (r−1)) and c(uiwk) = (n+k, if imod 4 ∈ {1,2}and k < r −n, k, otherwise. (Figure 12 illustrates the case (l, m, n, r) = (4,3,3,4).) Figure 12: 4-dynamic proper 7-coloring of P4×F3,3. •Case n<m+ 1 < r. Here, m > 2 and n+ 2 ≤r≤min{2m+ 1,2n}= 2n. From Lemma 8, we have that r+m≤χr(Pl×Fm,n). To prove that this lower bound is reached, we define an r-dynamic proper (r+m)-coloring cof Pl×Fm,n. More specifically, for each pair of non-negative integers i<land j < m, we define c(uivj) = (3j+i 2mod 3,if j < r −n, r+j, otherwise. SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 131 In addition, the following two subcases arise, for each pair of nonnegative integers i<land k < n. – Subcase m=n=r−2. c(uiwk) =                    6,if k= 0 and n > 3, 1 + i+1 2mod 3,if k= 1, 5 + k, if 2 ≤k < n −2, 3 + 1 + i+1 2mod 3,if ((k, n) = (0,3), k=n−2>1, n+ 3,if k=n−1. (Figure 13 illustrates the case m∈ {3,5}, for l= 5.) Figure 13: (m+ 2)-dynamic proper (2m+ 2)-coloring of the direct product P5×Fm,m, for m∈ {3,5}. – Subcase r > n + 2. c(uiwk) =                              6 + 1 + i+1 2mod 3,if k= 0 and n > 3, 1 + i+1 2mod 3,if k= 1, 3(k+ 1) + 1 + i+1 2mod 3,if 1 < k < min{n−2, r −n−1}, 2(r−n) + k+ 1,if r−n−1≤k < n −2, 3 + 1 + i+1 2mod 3,if ((k, n) = (0,3), k=n−2>1, 3(n−1) + 1 + i+1 2mod 3,if (k, r) = (n−1,2n), 2r−n−1,if k=n−1 and r < 2n. (Figure 14 illustrates the case (m, n, r)∈ {(4,3,6),(5,5,8)}, for l= 5.) SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 132 Figure 14: r-dynamic proper (r+m)-coloring of the direct product P5×Fm,n, for (m, n, r)∈ {(4,3,6),(5,5,8)}. •Case m+ 1 ≤n<r. Here, m+ 2 ≤r≤min{2m+ 1,2n}= 2m+ 1. From Lemma 8, r+n−2≤χr(Pl×Fm,n). To prove that this lower bound is reached, we define an appropriate r-dynamic proper (r+n−2)-coloring cof Pl×Fm,n. – Subcase m= 2. Here, (n, r)∈ {(3,4),(3,5),(4,5)}. For all i<l,j < m and k < n, it is enough to define c(uivj) = i 2mod 3 and c(uiwk) =                3 + i 2mod 2(r−4),if (k, n) = (0,3), 3 + i 2mod 3,if (k, n) = (0,4), 1 + i+1 2mod 3,if k= 1, 3 + 1 + i+1 2mod 3,if (k, n) = (2,4), r+n−3,if k=n−1. (Figure 15 illustrates the case l= 5.) – Subcase m > 2. Here, r+n−2≥m+n≥6. The map cis such that, for all i<l, j < m and k < n, we have that c(uiwk) = 2i 2+kmod nand c(uivj) =      n+j, if (j < 2m−r+ 2, j≥2m−r+ 2 and imod 4 ∈ {0,1}, n+r−2−m+j, if j≥2m−r+ 2 and imod 4 ∈ {2,3}. (Figure 16 illustrates the case (l, m, n, r) = (5,3,4,6).) SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 133 Figure 15: r-dynamic proper (r+n−2)-coloring of P5×F2,n, for (n, r)∈ {(3,4),(3,5),(4,5)}. Figure 16: 6-dynamic proper 8-coloring of P5×F3,4. Proposition 9. If 2n<r≤2m+ 1, then χr(Pl×Fm,n) =          2n+r−1,if r≤m+ 1, m+ 2n, if m+ 2 ≤r < m +n+ 2, n+r−2,if m+n+ 2 ≤rand (l, n)∈ {(3,4),(4,4)}, n+r−1,otherwise. . Proof. Here, n≤mand hence, m≥3. Let cbe an r-dynamic proper χr(Pl× Fm,n)-coloring of the direct product Pl×Fm,n. •Case r≤m+ 1. From Lemma 8, 2n+r−1≤χr(Pl×Fm,n). This lower bound is reached, because of the map csuch that, for all i<l,j < m and k < n, it is c(uivj)=2n+ (jmod (r−1)) and SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 134 c(uiwk) = (k, if imod 4 ∈ {0,1}, n+k, otherwise. (Figure 17 illustrates the case (l, m, n, r) = (4,7,3,7).) Figure 17: 7-dynamic proper 12-coloring of P4×F7,3. •Case m+ 2 ≤r < m +n+ 2. From Lemma 8, m+ 2n≤χr(Pl×Fm,n). This lower bound is reached, because of the map csuch that, for all i < l,j < m and k < n, we have that c(uivj) =      n+j, if imod 6 ∈ {0,5}and j < n, j, if imod 6 ∈ {3,4}and j < n, 2n+j, otherwise. and c(uiwk) =      k, if imod 6 ∈ {0,1}, n+k, if imod 6 ∈ {2,3}, 2n+k, otherwise. (Figure 18 illustrates the case (l, m, n) = (6,4,3), for r∈ {7,8}.) •Case m+n+ 2 ≤r. Since r≤2m+ 1 and n≤m, it must be n < m. From Lemma 8, n+r−2≤χr(Pl×Fm,n). In order to prove that this lower bound is reached for (l, n)∈ {(3,4),(4,4)}, it is enough to define the map cso that, for all i<l,j < m and k < 4, SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 135 Figure 18: r-dynamic proper 11-coloring of P6×F4,3, for r∈ {7,8}. c(uivj) =                0,if (i, j) = (3,0), 3,if (i, j) = (3,1), m+n+j, if (i= 0 and j < r −m−2, i= 3 and 1 < j < r −m−2, 4 + j, otherwise. c(uiwk) =                              0,if (i, k)∈ {(0,2),(1,0)}, 1,if (i, k)∈ {(1,1),(2,1)}, 2,if (i, k)∈ {(1,2),(2,2)}, 3,if (i, k)∈ {(0,1),(1,3)}, m+n, if (i, k)∈ {(2,0),(3,2)}, m+n+ 1,if (i, k)∈ {(2,3),(3,1)}, m+n+ 2,if (i, k)∈ {(0,0),(3,0)}, m+n+ 3,if (i, k)∈ {(0,3),(3,3)}. (Figure 19 illustrates the case (l, m, n, r) = (4,6,4,12).) Now, if (l, n)6∈ {(3,4),(4,4)}, then let us consider the pair of sets S= {c(u1w0), . . . , c(u1wn−1)}and S0={c(u0w0), . . . , c(u0wn−1), c(u2w0), ...,c(u2wn−1)}. If χr(Pl×Fm,n) = n+r−2, then Condition (1) applied to the vertex u0v0implies that the set Sis formed by ndistinct colors. SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 136 Figure 19: 12-dynamic proper 14-coloring of P4×F6,4. The same condition applied to the vertex u1w0implies that the set {c(u0v0), . . . , c(u0vm−1), c(u2v0), . . . , c(u2vm−1)}is formed by the remaining r−2 colors. As a consequence, for each non-negative integer i < n, the set c(N(u1wi)) ∩S0must contain two distinct colors of the set S. Furthermore, since r > 2n, Condition (1) applied to the vertex u1v0 implies that all the colors in the set S0are pairwise distinct. Hence, the map cwould require at least one extra color whenever n6= 4. From a similar reasoning, if n= 4 < l, then it must be {c(u2w1), c(u2w2)} ∈ S∩ {c(u3w0), . . . , c(u3wn−1)}. But this last intersection is empty, because of Condition (1) applied to vertex u2v0and the fact that r > 2n. So, again, an extra color is required. In order to prove that this extra (n+r−1)th color is sufficient in any of the described cases, it is enough to define the map cso that, for all i<l,j < m and k < n, c(uivj) =          m+j, if (imod 6 ∈ {2,3}and j≤r−m−2, imod 8 ∈ {6,7}and n≤j≤r−m−2, r−1 + j, if imod 6 ∈ {4,5}and j < n, j, otherwise. and c(uiwk) =      k, if imod 6 ∈ {3,4}, m+k, if imod 6 ∈ {0,5}, r−2 + k, if imod 6 ∈ {1,2}. (Figure 20 illustrates the case (l, m, n, r) = (8,6,4,12).) SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 137 Figure 20: 12-dynamic proper 15-coloring of P8×F6,4. 4 Some exact solutions Based on the results described in the previous section, let us finish our study by deducing some exact solutions of the r-dynamic coloring problem of direct products of paths with fan graphs. Firstly, we determine the case r≤7. Theorem 1. Let r∈ {1,2,3}. Then, χr(Pl×Fm,n) = (r+ 1,if r∈ {1,2}, 5,if r= 3. Proof. The result follows readily from Propositions 6 and 7. Theorem 2. It is verified that χ4(Pl×Fm,n) =                5,if (m, n) = (2,3), 6,if (m= 1, m= 2 and n≥4, 7,if (4≤min{m+ 1, n}, m≥n= 3. Proof. The result holds from the following study of cases: (a) Proposition 1 proves the case m= 1 and n≥4; (b) Proposition 4 proves the case (m, n) = (1,3); (c) Proposition 6 proves the case 4 ≤min{m+ 1, n}; (d) Proposition 7 proves the case m= 2 and n≥4; and (e) Proposition 8 proves the case n= 3 and m > 1. SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 138 Theorem 3. It is verified that χ5(Pl×Fm,n) =                                    6,if ((m, n)∈ {(1,3),(2,3)}, (m, n) = (1,4) and l6= 5, 7,if      m= 1 and n≥5, (l, m, n) = (5,1,4), (m, n)∈ {(2,4),(3,4)}, 8,if (min{m+ 1, n}<5≤min{2m+ 1, n}, m=n= 3, 9,if (5≤min{m+ 1, n}, n < 5≤m+ 1, Proof. The result holds from the following study of cases: (a) Proposition 1 proves the case m= 1 and n≥5; (b) Proposition 4 proves the case (m, n) = (1,3); (c) Proposition 5 proves the case (m, n) = (1,4); (d) Proposition 6 proves the case 5 ≤min{m+1, n}; (e) Proposition 7 proves the case min{m+ 1, n}<5≤min{2m+ 1, n}; and (f) Proposition 8 proves the cases n < 5≤ m+ 1 and (m, n)∈ {(2,3),(2,4),(3,3),(3,4)}. Theorem 4. It is verified that χ6(Pl×Fm,n) =                              8,if (m= 1, (m, n)∈ {(2,3),(2,4),(3,4)}, 9,if (m, n)∈ {(2,5),(3,3),(3,5),(4,5)}, 10,if      m= 2 and n≥6, min{m+ 1, n}<6≤min{2m+ 1, n}, (m, n)∈ {(4,3),(4,4)}, 11,if (6≤min{m+ 1, n}, n < 6≤m+ 1, Proof. The result holds from the following study of cases: (a) Lemma 6 proves the case m= 1; (b) Proposition 1 proves the case m= 2 and n≥6; (c) Proposition 2 proves the case (m, n)∈ {(2,4),(2,5)}; (d) Proposition 4 proves the case (m, n) = (2,3); (e) Proposition 6 proves the case 6 ≤min{m+ 1, n}; (f) Proposition 7 proves the case min{m+ 1, n}<6≤min{2m+ 1, n}; and (g) Proposition 8 proves the cases n < 6≤m+ 1 and (m, n)∈ {(3,3),(3,4), (3,5),(4,3),(4,4),(4,5)}. SOLVING THE DYNAMIC COLORING FOR DIRECT PRODUCTS OF PATHS WITH FAN GRAPHS 139 Theorem 5. It is verified that χ7(Pl×Fm,n) =                                              8,if (m, n) = (1,3), 9,if (m= 1 and n > 3, (m, n)∈ {(2,3),(2,4),(2,5),(3,3),(3,4)}, 10,if (m, n)∈ {(2,6),(4,3),(3,5),(4,5)}, 11,if (m= 2 and n≥7, (m, n)∈ {(3,6),(4,4),(4,6),(5,3),(5,6)}, 12,if      min{m+ 1, n}<7≤min{2m+ 1, n}, (m, n)∈ {(5,4),(5,5)}, n= 3 and 7≤m+ 1, 13,if (7≤min{m+ 1, n}, n < 7≤m+ 1. Proof. The result holds from the following study of cases: (a) Lemma 6 proves the case m= 1; (b) Proposition 1 proves the case m= 2 and n≥ 7; (c) Proposition 2 proves the case (m, n)∈ {(2,5),(2,6)}; (d) Proposition 3 proves the case (m, n) = (2,4); (e) Proposition 4 proves the case (m, n) = (2,3); (f) Proposition 6 proves the case 7 ≤min{m+ 1, n}; (g) Proposition 7 proves the case min{m+ 1, n}<7≤min{2m+ 1, n}; (h) Proposition 8 proves the cases n < 7≤m+ 1 and (m, n)∈ {(3,4),(3,5), (3,6),(4,4),(4,5),(4,6),(5,4),(5,5),(5,6)}; and (i) Proposition 9 proves the case n= 3 ≤m≤5. Finally, we solve the dynamic chromatic problem for the direct product of a path with either a simple fan graph or a double fan graph. Theorem 6. Let l > 2,n > 2and rbe three positive integers. Then, χr(Pl×F1,n) =                                  r+ 1,if      r∈ {1,2}, (n, r) = (3,5), (n, r) = (4,5) and l6= 5, r+ 2,if                r= 3, (n, r) = (3,4), (l, n, r) = (5,4,5), n≥r∈ {4,5}, 6≤r≤2n, 2n+ 2,if r > 2n.