The Circular Chromatic Index Of Some Graphs

All graphs considered in this paper are simple graphs. A k-edge coloring of a simple graph G is an assignment of k colors to the edges of G such that adjacent edges are colored differently. The minimum number k for which a graph G admits a k-edge coloring is the chromatic indexχ'(G) of G. In this paper we consider a refinement of the chromatic index which contains more information about the structure of the graph G.The circular chromatic index is a natural generalization of the chromatic index of a graph, obtained by carrying over the definition of the circular chromatic number, introduced by Vince, from vertex to edge coloring. Let G be a graph and let k, d be positive integers such that 2d≤k. Then a (k, d)-edge coloring of graph is an assignment c of colors {0, 1, ..., k - 1} to the edges of G such that for any two adjacent edges e₁, e₂ we have d≤|c(e-1) - c(e₂)|≤k- d. The circular chromatic indexχ'_c(G) of G is defined as the infimum of the ratio of k/d for which there exists a (k, d)-edge coloring of G.χ'_c(G) = inf {k/d : G has a (k, d)-edge coloring}.Theorem 0.1 If G is a graph on q edges thenχ'_c(G) = min{k/d : G has a (k, d) - edge coloring with k≤q}.Theorem 0.2 If G is class 1 thenχ'_c(G) =â–³(G). If G is class 2 thenâ–³(G) <χ'_c(G)≤△(G) + 1.Theorem 0.3 If G is class 2 then eitherχ'_c(G) =â–³(G) + 1 or â–³(G)+1/α'(G)≤χ'c(G)≤△(G)+α'(G)-1/α'(G),whereα'(G) is the edge independence number of G.All the circular chromatic index problems of graphs of class one are solved, but it is too difficult for the graphs of class two.In this paper, we'll try to give some results about the properties of some graphs of class two.The paper is divided into four chapters. In Chapter One, we introduce some basic conceptions of graph theory. In Chapter Two, some basic properties of the circular chromatic index of graphs are introduced. This two chapters are the base of following chapters.Chapter Three gives some results about the circular chromatic index of all the graphs whose vertices are no more than 7. The main results are the following properties.Theorem 0.4 There are 8 graphs of class 2 with the vertices no more than 7 in Fig 1. The circular chromatic index of the graphs are as follows:χ'_c(G₁) = 3,χ'_c(G₂) = 5/2,χ'_c(G₃)=4,χ'_c(G₄) = 9/2,χ'_c(G₅)=5,χ'_c(G₆) = 4,χ'_c(G₇) = 5,χ'_c(G₈)=5Theorem 0.5 G is a cartesian product graph C₃×C₃, then the circular chromatic index of G isχ'_c(G) =χ(G) = 5.In the Chapter Four, we will give the circular chromatic index of H_n.Theorem 0.6 Graph H_n is defined as follows:V(H_n) = {a_i, b_i, c_i, d_i, m_i, n_i : i = 1, ... , n}∪{ v }.E(H_n) = {a_ib_i,b_ic_i, c_id_i, d_im_i, m_in_i, n_ia_i, b_im_i, c_in_i, d_ia_i+1 : i = 1, ... , n}∪{va₁} where a_n+1 = v.Then for any positive integer n we haveχ'_c(H_n) = 3 + 1/n...