| Graph coloring problem is a main research area of graph theory, and is wildly applied in combinational optimization. It is proved that graph coloring is NP-complete. To the classical graph coloring, only the vertexes and edges are considered. With the development of application, new types of graph coloring problem are proposed. Total coloring is an important one of them. In 1965, Behzad showed the total coloring conjecture (TCC): For every simple graph G,χ"(G)≤△(G) + 2 whereχ"(G) is the total chromatic number and A(G) is the maximum degree of G. Conjecture TCC is proved to be true only for some special classes of graph, such as circles, complete graphs, the complete bipartite graphs, outerplanar graph and the planar graphs with maximum degree unequal to 6, 7, 8.Equitable total coloring is a special case of total coloring. The equitable total chromatic number of a graph G is the smallest integer k for which G has a k-total coloring such that the number of vertices and edges colored with each color differs by at most one. 1994, Hung-Lin Fu first investigated the equitable total coloring and conjectured that for every graph G, G has an equitable total k coloring for each k≥{χ"(G),△(G) + 2} .He proved the conjecture holds for a few special cases such as trees, complete graphs and the complete bipartite graphs. Wang proved that if G is a multigraph with maximum at most 3, then G has an 5 equitable total coloring.Let C_m□C_n be the Cartesian product of two cycles with length m and n, a lot of work has been done on the total chromatic number of this graphs. 1997, Seoud et al. proved thatχ"(C_m□C_n) =△+1 for m≥3 and n being an even number or a multiple of 3. 2003, Kemnitzand Marangio further proved thatχ"(C_m□C_n) =△+1 for m≥3 and n being a multiple of 5 too. This paper uses the method integrating with computer and mathematical analysis to study equitable total coloring of C_m□C_n. An algorithm is designed based on the condition to searchthe coloring. When m and n is large enough, by improve the efficiency of the algorithm to find as much coloring as possible. It is proved that the equitable total chromatic number of C_m□C_n is 5 for all m≥3 and n≥3. The equitable total coloring of another Cartesian product graph P_m□C_n is studied in this paper, and proved that the equitable total chromatic number of P_m□C_n is 5 for all m≥3 and n≥3 too. |
