Premium
On the Total Coloring of Graphs Embeddable in Surfaces
Author(s) -
Zhao Yue
Publication year - 1999
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610799007668
Subject(s) - combinatorics , mathematics , graph , surface (topology) , degree (music) , euler characteristic , discrete mathematics , physics , geometry , acoustics
The paper shows that any graph G with the maximum degree Δ( G ) ⩾ 8, which is embeddable in a surface Σ of Euler characteristic χ(Σ) ⩾ 0, is totally (Δ( G )+2)‐colorable. In general, it is shown that any graph G which is embeddable in a surface Σ and satisfies the maximum degree Δ( G ) ⩾ (20/9) (3−χ(Σ))+1 is totally (Δ( G )+2)‐colorable.