Search

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":["M. Behzad, The total chromatic number of a graph Combinatorial\nMathematics and its Applications, Proceedings of the Conference Oxford\nAcademic Press N. Y. 1-9, 1971.","V. G. Vizing, On evaluation of chromatic number of a p-graph (in\nRussian) Discrete Analysis, Collection of works of Sobolev Institute of\nMathematics SB RAS 3 3-24, 1964.","X. Zhou, Y. Matsuo, T. Nishizeki, List total colorings of series-parallel\nGraphs, Computing and Combinatorics,Lecture Notes in Comput. Sci.\n2697, Springer Berlin, 172-181, 2003.","M. Rosenfeld, On the total coloring of certain graphs. Israel J. Math. 9\n396-402, 1971.","N. Vijayaditya, On total chromatic number of a graph, J. London Math.\nSoc. 3 405-408, 1971.","H. P. Yap, Total colourings of graphs. Bull. London Math. Soc. 21\n159-163, 1989.","A. V. Kostochka, The total colorings of a multigraph with maximal\ndegree 4. Discrete Math. 17, 161-163, 1977.","A. V. Kostochka, Upper bounds of chromatic functions of graphs (in\nRussian). Doctoral Thesis, Novosibirsk, 1978.","A. V. Kostochka, Exact upper bound for the total chromatic number\nof a graph (in Russian). In: Proc. 24th Int. Wiss. Koll.,Tech. Hochsch.\nIlmenau,1979 33-36, 1979.\n[10] H. P. Yap, Total coloring of graphs, Lecture Note in Mathematics Vol.\n1623, Springer Berlin, 1996.\n[11] R. L. Brooks, On coloring the nodes of a network, Proc. Cambridge\nPhil. Soc. 37 194-197, 1941.\n[12] D. B. West, Introduction to Graph Theory, Prentice Hall, New Jersey,\n2001.\n[13] S. Fiorini, R. J. Wilson, Edge Coloring of Graphs, Pitman London, 1977.\n[14] M. Bezhad, G. Chartrand, J. K. Cooper, The colors numbers of complete\ngraphs, J. London Math. Soc. 42 225-228, 1967."]}

A $(k,t)$-list assignment $L$ of a graph $G$ is a mapping which assigns a set of size $k$ to each vertex $v$ of $G$ and $|\bigcup_{v\in V(G)}L(v)|=t$. A graph $G$ is $(k,t)$-choosable if $G$ has a proper coloring $f$ such that $f(v)\in L(v)$ for each $(k,t)$-list assignment $L$.In 2011, Charoenpanitseri, Punnim and Uiyyasathian proved that every $n$-vertex graph is $(2,t)$-choosable for $t\geq 2n-3$ and every $n$-vertex graph containing a triangle is not $(2,t)$-choosability for $t\leq 2n-4$. Then a complete result on $(2,t)$-choosability of an $n$-vertex graph containing a triangle is revealed. Moreover, they showed that an $n$-vertex triangle-free graph is $(2,t)$-choosable for $t\geq 2n-6$.In this paper, we first prove that an $n$-vertex graph containing $K_{3,3}-e$ is not $(2,t)$-choosable for $t\leq 2n-7$. Then we deeply investigates $(2,t)$-choosablity of an $n$-vertex graph containing neither a triangle nor $K_{3,3}-e$.