Consecutive Colorings Of Two Classes Of Graphs

Given a graph G, a proper edge coloring of G with colors 1, 2, 3,…is consecutiveif the colors of edges incident to each vertex form an interval of integers. The deficiency def(G) of G is the minimum number of pendant edges whose attachment makes the resultinggraph consecutively colorable. This article has three chapters, which mainly study the consecutive colorings of two families of graphs.In Chapter 1, some terminology, notation and basic results in the thesis are given.In Section 2.1, some relative results are given. If G is a graph with induced subgraphs G₁, G₂ and S, such that G = G₁∪G₂ and S = G₁∩G₂, we say that G arises from G₁ and G₂ by pasting these graphs together along S. In particular, if S = K₁ and V(S) - {v}, then we say that G is the paste of G₁ and G₂ at the vertex v, denoted by G = G₁∨_v G₂. A tree-cycle graph is a connected graph in which each edge belongs to one cycle at most. Especially, a tree-cycle graph which is obtained by pasting some cycles at the same vertex is called a flower graph. The consecutive colorings of tree-cycle graph is mainly studied in Section 2.2, and we obtain the results as follows:Theorem 2.2.7 Let G be a flower graph. ThenTheorem 2.2.9 Let G = G₁∨_w G₂, and G₁, G₂ be flower graphs. ThenTheorem 2.2.10 Let G be a tree-cycle graph composed of some odd cycles. Ifε(G) isodd, then def(G)≥1.Theorem 2.2.11 Let G be a tree-cycle graph which is obtained by pasting an odd cycle at every vertex of the same odd cycle. Then def(G) = 1.Theorem 2.2.12 Let G be a tree-cycle graph which is obtained by pasting an odd cycle at every but one vertex of the same odd cycle. Then def(G) = 1.Let P₁,P₂,…, P_m be m (m≥4) paths whose length is n - 1 (n≥3) in turn from up to down , the vertices of the ith path are v_i1, v_i2,…, v_in (1≤i≤m) in turn. Then the graph obtained by connecting the vertices v_ij and v_i+1,j,v_i+3,j+2(1≤j≤n) is called an m×n graph. In Chapter 3, we prove that the m×n graph is consecutively colorable.