10008947

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

**Abstract:**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.

**References:**

[1] M. Behzad, The total chromatic number of a graph Combinatorial
Mathematics and its Applications, Proceedings of the Conference Oxford
Academic Press N. Y. 1-9, 1971.

[2] V. G. Vizing, On evaluation of chromatic number of a p-graph (in
Russian) Discrete Analysis, Collection of works of Sobolev Institute of
Mathematics SB RAS 3 3-24, 1964.

[3] X. Zhou, Y. Matsuo, T. Nishizeki, List total colorings of series-parallel
Graphs, Computing and Combinatorics,Lecture Notes in Comput. Sci.
2697, Springer Berlin, 172-181, 2003.

[4] M. Rosenfeld, On the total coloring of certain graphs. Israel J. Math. 9
396-402, 1971.

[5] N. Vijayaditya, On total chromatic number of a graph, J. London Math.
Soc. 3 405-408, 1971.

[6] H. P. Yap, Total colourings of graphs. Bull. London Math. Soc. 21
159-163, 1989.

[7] A. V. Kostochka, The total colorings of a multigraph with maximal
degree 4. Discrete Math. 17, 161-163, 1977.

[8] A. V. Kostochka, Upper bounds of chromatic functions of graphs (in
Russian). Doctoral Thesis, Novosibirsk, 1978.

[9] A. V. Kostochka, Exact upper bound for the total chromatic number
of a graph (in Russian). In: Proc. 24th Int. Wiss. Koll.,Tech. Hochsch.
Ilmenau,1979 33-36, 1979.

[10] H. P. Yap, Total coloring of graphs, Lecture Note in Mathematics Vol.
1623, Springer Berlin, 1996.

[11] R. L. Brooks, On coloring the nodes of a network, Proc. Cambridge
Phil. Soc. 37 194-197, 1941.

[12] D. B. West, Introduction to Graph Theory, Prentice Hall, New Jersey,
2001.

[13] S. Fiorini, R. J. Wilson, Edge Coloring of Graphs, Pitman London, 1977.

[14] M. Bezhad, G. Chartrand, J. K. Cooper, The colors numbers of complete
graphs, J. London Math. Soc. 42 225-228, 1967.