Upper Bounds for the Maximum Span in Interval Total Colorings of Graphs


  • Petros A. Petrosyan Institute for Informatics and Automation Problems of NAS RA
  • Nerses A. Khachatryan Yerevan State University


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 to each vertex v together with v are colored by dG(v) + 1 consecutive colors, where dG(v) is the degree of a vertex v in G. In this paper we prove that if a connected graph G with n vertices admits an interval total t-coloring, then t≤2n-1. Furthermore, we show that if G is a connected r-regular graph with n vertices which has an interval total t-coloring and n≥2r+2, then this upper bound can be improved to 2n ¡ 3. We also give some other upper bounds for the maximum span in interval total colorings of graphs.

Author Biography

Nerses A. Khachatryan, Yerevan State University

Department of Informatics and Applied Mathematics


A.S. Asratian, C.J. Casselgren, “On interval edge colorings of (α, β)-biregular bipartite graphs", Discrete Mathematics 307, pp. 1951-1956, 2006.

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

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

M.A. Axenovich, “On interval colorings of planar graphs", Congr. Numer. 159, pp. 77-94, 2002.

M. Behzad, “Graphs and their chromatic numbers", Ph.D. thesis, Michigan State University, 1965.

K. Giaro, M. Kubale and M. Malafiejski, “Consecutive colorings of the edges of general graphs", Discrete Math. 236, pp. 131-143, 2001.

R.R. Kamalian, “Interval edge-colorings of graphs", Doctoral Thesis, Novosibirsk, 1990 (in Russian).

P.A. Petrosyan, “Interval total colorings of complete bipartite graphs", Proceedings of the CSIT Conference, pp. 84-85, 2007.

P.A. Petrosyan, “Interval total colorings of certain graphs", Mathematical Problems of Computer Science, Vol. 31, pp. 122-129, 2008.

P.A. Petrosyan, A.S. Shashikyan, “On interval total colorings of trees", Mathematical Problems of Computer Science, Vol. 32, pp. 70-73, 2009.

P.A. Petrosyan, A.Yu. Torosyan, “Interval total colorings of complete graphs", Proceedings of the CSIT Conference, pp. 99-102, 2009.

P.A. Petrosyan, “Interval edge-colorings of complete graphs and n-dimensional cubes", Discrete Mathematics 310, pp. 1580-1587, 2010.

V.G. Vizing, ”Chromatic index of multigraphs", Doctoral Thesis, Novosibirsk, 1965 (in Russian).

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




How to Cite

Petrosyan, P. A. ., & Khachatryan, N. A. . (2021). Upper Bounds for the Maximum Span in Interval Total Colorings of Graphs. Mathematical Problems of Computer Science, 35, 19–25. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/281

Most read articles by the same author(s)