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
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
