Total coloring of 1-toroidal graphs with maximum degree at least 11 and no adjacent triangles |
| |
Authors: | Tao Wang |
| |
Institution: | 1.Institute of Applied Mathematics,Henan University,Kaifeng,People’s Republic of China |
| |
Abstract: | A total coloring of a graph G is an assignment of colors to the vertices and the edges of G such that every pair of adjacent/incident elements receive distinct colors. The total chromatic number of a graph G, denoted by \(\chi ''(G)\), is the minimum number of colors in a total coloring of G. The well-known total coloring conjecture (TCC) says that every graph with maximum degree \(\Delta \) admits a total coloring with at most \(\Delta + 2\) colors. A graph is 1-toroidal if it can be drawn in torus such that every edge crosses at most one other edge. In this paper, we investigate the total coloring of 1-toroidal graphs, and prove that the TCC holds for the 1-toroidal graphs with maximum degree at least 11 and some restrictions on the triangles. Consequently, if G is a 1-toroidal graph with maximum degree \(\Delta \) at least 11 and without adjacent triangles, then G admits a total coloring with at most \(\Delta + 2\) colors. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|