Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 30123
##### 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.

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

References:

 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.
 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.
 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.
 M. Rosenfeld, On the total coloring of certain graphs. Israel J. Math. 9 396-402, 1971.
 N. Vijayaditya, On total chromatic number of a graph, J. London Math. Soc. 3 405-408, 1971.
 H. P. Yap, Total colourings of graphs. Bull. London Math. Soc. 21 159-163, 1989.
 A. V. Kostochka, The total colorings of a multigraph with maximal degree 4. Discrete Math. 17, 161-163, 1977.
 A. V. Kostochka, Upper bounds of chromatic functions of graphs (in Russian). Doctoral Thesis, Novosibirsk, 1978.
 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.
 H. P. Yap, Total coloring of graphs, Lecture Note in Mathematics Vol. 1623, Springer Berlin, 1996.
 R. L. Brooks, On coloring the nodes of a network, Proc. Cambridge Phil. Soc. 37 194-197, 1941.
 D. B. West, Introduction to Graph Theory, Prentice Hall, New Jersey, 2001.
 S. Fiorini, R. J. Wilson, Edge Coloring of Graphs, Pitman London, 1977.
 M. Bezhad, G. Chartrand, J. K. Cooper, The colors numbers of complete graphs, J. London Math. Soc. 42 225-228, 1967.