Total Colorings of $F_5$-Free Planar Graphs with Maximum Degree 8

  • Jian Chang
  • Jian-Liang Wu
  • Hui-Juan Wang
  • Zhan-Hai Guo
Keywords: Planar graph, Total coloring, Cycle

Abstract

The total chromatic number of a graph $G$, denoted by $\chi′′(G)$, is the minimum number of colors needed to color the vertices and edges of $G$ such that no two adjacent or incident elements get the same color. It is known that if a planar graph $G$ has maximum degree $\Delta ≥ 9$, then $\chi′′(G) = \Delta + 1$. The join $K_1 \vee P_n$ of $K_1$ and $P_n$ is called a fan graph $F_n$. In this paper, we prove that if $G$ is a $F_5$-free planar graph with maximum degree 8, then $\chi′′(G) = 9$.
Published
2014-03-17
Article Number
P1.56