1

10008947

Total Chromatic Number of Δ-Claw-Free 3-Degenerated Graphs

The total chromatic number χ"(G) of a graph G is the
minimum number of colors needed to color the elements (vertices
and edges) of G such that no incident or adjacent pair of elements
receive the same color Let G be a graph with maximum degree Δ(G).
Considering a total coloring of G and focusing on a vertex with
maximum degree. A vertex with maximum degree needs a color and
all Δ(G) edges incident to this vertex need more Δ(G) + 1 distinct
colors. To color all vertices and all edges of G, it requires at least
Δ(G) + 1 colors. That is, χ"(G) is at least Δ(G) + 1. However,
no one can find a graph G with the total chromatic number which
is greater than Δ(G) + 2. The Total Coloring Conjecture states that
for every graph G, χ"(G) is at most Δ(G) + 2. In this paper, we prove that the Total Coloring Conjectur for a
Δ-claw-free 3-degenerated graph. That is, we prove that the total
chromatic number of every Δ-claw-free 3-degenerated graph is at
most Δ(G) + 2.