# On Interval Total Colorings of Trees

## 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 T (T ≠ K1) is a tree and Δ(T) + 2 ≤ t ≤ M(T) then T has an interval total t-coloring, where Δ(T) is the maximum degree of vertices in T and M(T) is a parameter which can be effectively found for any T.

## References

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.

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

*Mathematical Problems of Computer Science*,

*32*, 70–73. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/367

## Issue

## Section

## License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.