# Interval Total Colorings of Certain Graphs

## Abstract

An interval total t-coloring of a graph G is a total coloring of G with colors 1, 2,…t such that at least one vertex or edge of G is colored by i; i = 1, 2,…t, and the edges incident with each vertex v together with v are colored by (dG(v) + 1) consecutive colors, where dG(v) is the degree of the vertex v in G. It is proved that complete graphs, complete bipartite graphs and n-dimensional cubes have interval total colorings and bounds are found for the possible number of colors in such colorings.

## References

A.S. Asratian, T.M.J. Denley, R. Haggkvist, Bipartite Graphs and Their Applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, 1998.

A.S. Asratian, R.R.Kamalian, “Interval colorings of edges of a multigraph", Appl. Math. 5, pp. 25-34, 1987.

A.S. Asratian, R.R.Kamalian, “Investigation on interval edge-colorings of graphs", Journal of Combin. Theory, Ser. B, vol. 62, pp. 34-43, 1994.

M. Behzad, Graphs and Their Chromatic Numbers, Ph.D. thesis, Michigan State University, 1965.

M. Behzad, G.Chartrand, J.K.Cooper, “The colour numbers of complete graphs", Journal of London Math. Soc. 42, pp. 226-228, 1967.

O.V. Borodin, “On the total colouring of planar graphs", J. Reine Angew. Math. 394, pp. 180-185, 1989.

O.V. Borodin, A.V. Kostochka, D.R. Woodall, “Total colorings of planar graphs with large maximum degree", Journal of Graph Theory 26, pp. 53-59, 1997.

K.H. Chew, H.P. Yap, “Total chromatic number of complete r-partite graphs", Journal of Graph Theory 16, pp. 629-634, 1992.

T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley Interscience Seriesin Discrete Mathematics and Optimization, 1995.

A.V. Kostochka, “The total coloring of a multigraphs with maximal degree 4", Discrete Mathematics 17, pp. 161-163, 1977.

A.V. Kostochka, “The total coloring of a multigraphs with maximal degree 5 is at most seven", Discrete Mathematics 162, pp. 199-214, 1996.

P.A. Petrosyan, “Interval edge colourings of complete graphs and n-cubes", Mathematical Problems of Computer Science, vol. 25, pp. 5-8, 2006.

M. Rosenfeld, “On the total coloring of certain graphs", Israel J. Math. 9, pp. 396-402, 1971.

D.P. Sanders, Y. Zhao, “On total 9-coloring planar graphs of maximum degree seven", Journal of Graph Theory 31, pp. 67-73, 1999.

N. Vijayaditya, “On the total chromatic number of a graph", Journal of London Math. Soc. (2) 3, pp. 405-408, 1971.

V.G. Vizing, “On an estimate of the chromatic class of a p-graph", Diskret. Analiz 3, pp. 25-30, 1964.

D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 1996.

H.P. Yap, Total Colorings of Graphs, Lecture Notes in Mathematics 1623, Springer-Verlag, Berlin, 1996.

Z. Zhang, J. Zhand, J.Wang, “The total chromatic numbers of some graphs", Scientia Sinica A 31, pp. 1434-1441, 1988.

## Downloads

## Published

## How to Cite

*Mathematical Problems of Computer Science*,

*31*, 122–129. Retrieved from https://mpcs.sci.am/index.php/mpcs/article/view/399