Consecutive Colorings Of Some Graphs

The consecutive coloring problem is one of popular problems which have wide applications in combinatorial analysis and scheduling theory. In 1987 Asratian and Kamalian introduced the concept of consecutive colorings: Given a graph G, a proper edge coloring of C with colors 1, 2, 3…is consecuive if the colors of edges incident to each vertex form an interval of integers. Many graphs do not consecutive colorings. In order to give a measure of how close it comes to having a consecutive colorings, we introduce a new graph invariant: the consecutive colorings deficiency of a graphs. The deficiency def(G) of G is the minimum number of pendant edges whose attachment makes G consecutively colorable. This article consists of three chapters, which mainly study the consecutive colorings of some graphs.In Chapter 1, after a short introduction to the used basic notation, terminology and some concepts on graphs, we give in section 1.2 basic results on the consecutive colorings.Chapter 2 deals with the consecutive colorings of some cyclic graphs. In this Chapter,according to the structure and the property of tricyclic graphs and the definition of consecutive colorings, the consecutive colorings and the deficiency are obtianed. Then we extend these results to a class of k-cyclic graphs, by using the thought of induction and reduction to absurdity. The main results are given as follows:(1) Let G be the union of four internally disjoint (u,v) paths. Then(2) Let C₁,C₂,C₃ be three disjoint cycles, and P_i(i = 1,2) be a (V(C_i), V(C_i+1)) path, such that P₁ and P₂ be two disjoint paths. If G be the union of C₁, C₂, C₃, P₁, P₂, then def(G) = 0.(3) Let C₁, C₂,…,C_n be n(n≥1) cycles with exactly one vertex in common, and let G be the union of these cycles. ThenThe consecutive colorings of some Cartesian product graphs are studied in Chapter3. By using induction and instructure method, we obtian the deficiency of the Cartesian product graphs P_n×P_m and C_m×P_n. The main results are given as follows:(1) Let G be the Cartesian product of two disjoint paths P_n and P_m. Then def(G) = 0.(2) Let C_m be a cycle of length m≥3. and let P_n be a path of length n≥0 disjoint from C_m. If G is the Cartesian product of C_m and P_n. then def(G)≤1.