Consecutive Edge-Colorings Of Cacti

Given a simple graph G, a proper edge-coloring of G with colors 1,2,3,...is called consecutive if the colors represented at each vertex form an interval ofintegers [2]. The consecutive edge-coloring of graphs corresponds to schedulingproblem without waiting periods. Not all graphs have consecutive colorings.The deficiency def(G) of G is the minimum number of pendant edges whoseattachment to G makes it consecutively colorable [9].In general the work to verify whether a graph admits a consecutive coloringis di?cult, and there is a few of such graphs characterized. In fact, Sevastjanov[3] proved that it is NP-complete to decide if a given bipartite graph G has aconsecutive coloring.A cactus is a graph whose blocks are cycles or graphs K2. From this it followsthat any two di?erent cycles of a cactus have at most one vertex in common.Denote by o(G) the number of odd cycles of G, and by Fn? the graph that consistsof n triangles with a common vertex. If G is a graph with induced subgraphs G1and G2, such that G = G1∪G2 and G1∩G2 = K1, we say that G is the pasteof G1 and G2 at v, where v∈V (G1∩G2), denoted by G = G1∨v G2.In this thesis, we focus on the consecutive edge-coloring problem for cacti.We determine the deficiency of the cacti with no more than two odd cycles,give, for a cactus with an even number of odd cycles and without cut edges, asu?cient condition to be consecutively colorable, and show that the cacti with anodd number of odd cycles and without cut edges are not consecutively colorable.In addition, we characterize two classes of cacti whose deficiency equal 1. Thefollowing are our main results.1. Let G be a cactus and o(G) 2. Then def(G) = 1 if G has no cut edgeand o(G) = 1, and def(G) = 0 otherwise.2. Let G be a cactus without cut edges and let o(G) be even. If there is atleast one vertex v∈V (C) such that dG(v) = 2 for any odd cycle C of G,then def(G) = 0.