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.
 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
 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
 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,
 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.