Upper Bounds for the Maximum Span in Interval Total Colorings of 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 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.
References
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.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
