论文部分内容阅读
It is proved that if G is a (△+1)-colorable graph, so are the graphs G×Pn and C×Cn, where Pn and Cn are respectively the path and cycle with n vertices, and △ the maximum edge degree of the graph. The exact chromatic numbers of the product graphs Pr1×Pr1×...×Prn× and C3k×C2m1×C2m2×...×C2mn are also presented. Thus the total coloring conjecture is proved to be true for many other graphs.