Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Article

HOME ALL ARTICLES View

Bull. Korean Math. Soc. 2016; 53(1): 139-151

Printed January 31, 2016

https://doi.org/10.4134/BKMS.2016.53.1.139

Copyright © The Korean Mathematical Society.

Total colorings of planar graphs with maximum degree at least 7 and without adjacent 5-cycles

Xiang Tan

Shandong University of Finance and Economics

Abstract

A $k$-total-coloring of a graph $G$ is a coloring of $V\cup E$ using $k$ colors such that no two adjacent or incident elements receive the same color. The total chromatic number $\chi''(G)$ of $G$ is the smallest integer $k$ such that $G$ has a $k$-total-coloring. Let $G$ be a planar graph with maximum degree $\Delta$. In this paper, it's proved that if $\Delta\geq 7$ and $G$ does not contain adjacent 5-cycles, then the total chromatic number $\chi''(G)$ is $\Delta+1$.

Keywords: planar graph, total coloring, adjacent 5-cycle

MSC numbers: 05C15