Discussiones Mathematicae Graph Theory (Nov 2018)

Total Colorings of Embedded Graphs with No 3-Cycles Adjacent to 4-Cycles

  • Wang Bing,
  • Wu Jian-Liang,
  • Sun Lin

DOI
https://doi.org/10.7151/dmgt.2058
Journal volume & issue
Vol. 38, no. 4
pp. 977 – 989

Abstract

Read online

A total-k-coloring of a graph G is a coloring of V ∪ E using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number χ′′(G) of G is the smallest integer k such that G has a total-k-coloring. Let G be a graph embedded in a surface of Euler characteristic ε ≥ 0. If G contains no 3-cycles adjacent to 4-cycles, that is, no 3-cycle has a common edge with a 4-cycle, then χ′′(G) ≤ max{8,Δ+1}.

Keywords