Consecutive Edge-coloring Of Some Families Of Graphs

Given a graph G, an edge-coloring of G with colors 1,2,3,... is consecutive if the colors of edges incident to each vertex form an interval of integers. The consecutive edge-coloring of graphs have important applications in scheduling theory, which was introduced by Kubale in [9] and studied by the authors in [4,6,7,9]. The deficiency 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, is a graph consisting of m internal disjoint (u, v)-paths, where 2 ≤ m < ∞. Denote by P₁, P₂,..., P_m all the (u,v)-paths of θ_m, â—‡(θ_m) the number of even paths among them and o(θ_m) the number of odd paths among them. Let l(Pi) be the length of Pi and l_max(θ_m) = max_{1≤i≤m} l(Pi). F_n^* = K₁ + nK₂ is a graph that contains n triangles sharing a common vertex.Let Gbea graph of 0-deficient. By the span s(G, c) of coloring c we mean the number of colors used in the consecutive edge-coloring. By s(G)(S(G)) we denote the minimum (maximum) span among all consecutive edge-coloring of G, respectively.In this thesis, we completely characterize the consecutive edge-coloring problem for θ_m and F_n^*. Some graphs G, def(G) = 1, are also considered. In addition, we get three bounds on S(θ_m), s(θ_m) and de f(G). The following are our main results.1. (Theorem 3.6) Let θ_m be a generalized θ-graph. Thenif â—‡(θ_m) is odd and â—‹(θ_m) is odd;...