Consecutive edge-coloring of the generalized θθ-graph

Given a graph G, an edge-coloring of G   with colors 1,2,3,…1,2,3,… is consecutive if the colors of edges incident to each vertex are distinct and form an interval of integers. The consecutive edge-coloring of graphs has important applications in scheduling theory and was studied by the authors in [A.S. Asratian, T.M.J. Denley, R. Häggkviist, Bipartite Graphs and their Applications, Cambridge University Press, Cambridge, 1998; K. Giaro, M. Kubale, M. Malafiejski, compact scheduling in open shop with zero-one time operations, Infor 37 (1999) 37–47; K. Giaro, M. Kubale, Compact scheduling of zero-one time operations in multistage system, Discrete Appl. Math. 145 (2004) 95–103]. The deficiency def(G)def(G) of G is the minimum number of pendant edges whose attachment to G   makes it consecutively colorable. A generalized θθ-graph, denoted by θmθm, is a graph consisting of m   internal disjoint (u,v)(u,v)-paths, where 2⩽m<∞2⩽m<∞. In this paper, we completely determine the deficiency def(θm)def(θm) of θmθm and prove that S(θm)⩽lmax(θm)+Δ-1S(θm)⩽lmax(θm)+Δ-1, where S(θm)S(θm) is the maximum number of colors allowing a consecutive edge-coloring and lmax(θm)lmax(θm) is the length of the longest (u,v)(u,v)-paths in θmθm.