# On Interval Total Colorings of Doubly Convex Bipartite Graphs

## Abstract

A bipartite graph G = (U; V;E) is doubly convex if all its vertices from the U can be numbered 1, 2,..., |U| and all vertices from V can be numbered 1, 2,…, |V| in such a way that for any vertex of G the set of numbers assigned to neighbors is an interval of integers. 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 all doubly convex bipartite graphs have an interval total coloring. Furthermore, we give some bounds for the minimum and the maximum span in interval total colorings of these graphs.

## References

A.S. Asratian, T.M.J. Denley, R. Haggkvist, Bipartite Graphs and their Applications, Cambridge University Press, Cambridge, 1998.

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, N.A. Khachatryan, “Interval total colorings of graphs with a spanning star", Mathematical Problems of Computer Science, Vol. 32, pp. 78-85, 2009.

P.A. Petrosyan, A.S. Shashikyan, “On interval total colorings of bipartite graphs", Proceedings of the CSIT Conference, pp. 95-98, 2009.

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

A.S. Shashikyan, “On interval total colorings of bipartite graphs", Master's Thesis, Yerevan State University, 2009, 29 p.

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*,

*33*, 54–58. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/331

## Issue

## Section

## License

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