Interval Total Colorings of Complete Multipartite Graphs and Hypercubes
Keywords:
Total coloring, Interval total colorin, Interval coloring, Complete multipartite graph, HypercubeAbstract
A total coloring of a graph G is a coloring of its vertices and edges such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. An interval total t-coloring of a graph G is a total coloring of G with colors 1; : : : ;t such that all colors are used, 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 all complete multipartite graphs with the same number of vertices in each part are interval total colorable. Moreover, we also give some bounds for the minimum and the maximum span in interval total colorings of these graphs. Next, we investigate interval total colorings of hypercubes Qn. In particular, we prove that Qn (n ¸ 3) has an interval total t-coloring if and only if n + 1 • t • (n+1)(n+2) 2.
References
A. S. Asratian, T.M.J. Denley and R. Haggkvist, Bipartite Graphs and their Applications, Cambridge University Press, Cambridge, 1998.
A.S. Asratian and R.R. Kamalian, “Interval colorings of edges of a multigraph", Appl. Math., vol. 5, pp. 25-34, 1987.
M. Behzad, G. Chartrand and J.K. Cooper, “The colour numbers of complete graphs", J. London Math. Soc., vol. 42, pp. 226-228, 1967.
J. C. Bermond, “Nombre chromatique total du graphe r-parti complet", J. London Math. Soc., vol. 2, no. 9, pp. 279-285, 1974.
P.A. Petrosyan, “Interval total colorings of complete bipartite graphs", Proceedings of the CSIT Conference, Yerevan, 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, “Interval edge-colorings of complete graphs and n-dimensional cubes", Discrete Math. 310, pp. 1580-1587, 2010.
P. A. Petrosyan and H. H. Khachatrian, “Interval total colorings of complete multipartite graphs", 4-th Polish Combinatorial Conference, Bedlewo, Poland, p. 35, 2012.
P. A. Petrosyan, H. H. Khachatrian and H.G. Tananyan, “Interval edge-colorings of Cartesian products of graphs I", Discussiones Mathematicae Graph Theory, vol. 33, no. 3, pp. 613-632, 2013.
P. A. Petrosyan and N. A. Khachatryan, “Interval total colorings of graphs with a spanning star", Mathematical P roblems of Computer Science, vol. 32, pp. 78-85, 2009.
P. A. Petrosyan and N.A. Khachatryan, “Upper bounds for the maximum span in interval total colorings of graphs", Mathematical Problems of Computer Science, vol. 35, pp. 19-25, 2011.
P. A. Petrosyan and N. A. Khachatryan, “On interval total colorings of the Cartesian products of graphs", Proceedings of the CSIT Conference, Yerevan, pp. 85-86, 2013.
P. A. Petrosyan and A. S. Shashikyan, “On interval total colorings of trees", Mathematical Problems of Computer Science, vol. 32, pp. 70-73, 2009.
P.A. Petrosyan and A.S. Shashikyan, “On interval total colorings of bipartite graphs", Proceedings of the CSIT Conference, Yerevan, pp. 95-98, 2009.
P.A. Petrosyan and A.S. Shashikyan, “On interval total colorings of doubly convex bipartite graphs", Mathematical Problems of Computer Scienc, vol. 33, pp. 54-58, 2010.
P. A. Petrosyan, A. S. Shashikyan and A.Yu. Torosyan, “Interval total colorings of bipartite graphs", Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Cologne, Germany, pp. 133-136, 2010.
P. A. Petrosyan, A. S. Shashikyan, A.Yu. Torosyan and N.A. Khachatryan, “Interval total colorings of graphs", 6th Cracow Conference on Graph Theory "Zgorzelisko'10", Zgorzelisko, Poland, p. 11, 2010.
P.A. Petrosyan and A.Yu. Torosyan, “Interval total colorings of complete graphs", Proceedings of the CSIT Conference, Yerevan, pp. 99-102, 2009.
A .S. Shashikyan, “On interval total colorings of bipartite graphs", Master's Thesis, Yerevan State University, 29p, 2009.
D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 1996.
H.P. Yap, Total Colorings of Graphs, Lecture Notes in Mathematics 1623, SpringerVerlag, 1996.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
