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.

Authors:

• Wongsakorn Charoenpanitseri

Keywords:

• Total colorings
• the total chromatic number
• 3-degenerated.

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.