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.