全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

Total coloring of 1-toroidal graphs of maximum degree at least 11 and no adjacent triangles

Full-Text   Cite this paper   Add to My Lib

Abstract:

A {\em 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 {\em total chromatic number} of a graph $G$, denoted by $\chiup''(G)$, is the minimum number of colors needed in a total coloring of $G$. The most 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 {\em 1-toroidal} if it can be drawn on 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.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133