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

Authors: Wongsakorn Charoenpanitseri

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.

Keywords: Total colorings, the total chromatic number, 3-degenerated.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1316590

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.