Fractional Colorings Of Graphs

In this article, we use[x] for the maximum integer which is no more than the real number x, we use[x] for the minimum integer which is no less than the real number x. We denote by|S| the mumber of the elements in the set.All graphs considered are simple, finite and undirected. For a graph G. we denote the vertex set and the edge set of G by V(G) and E(G). respectively. We use d_G(v) for the degree of u in V(G) andâ–³(G) for the maximum degree of G andδ(G) for the minimum degree of G. Let G[V′] denote the induced subgraph of G with vertex set V′and G[E′] denote the induced subgraph of G with edge set E′. We denote by K_n the complete graph on n vertices. We use the symbolsω(G) andκ(G) to denote the number of components of G and the connectivity of G. The independence number of G is denoted byα(G) and the chromatic number of G is denoted byχ(G). For any undefined notation and terminology. we refer the reader to[1].The definition of fractional coloring is given in|6| by E. Scheinerman and D. Ullman. it is fractional generalization of coloring of graphs. Obtain every graph's fractional chromatic number is NP-hard.A mapping C from the collectionζof independent sets of a graph G to the interval[0. 1] is a fractional-coloring if for every vertex x of G. we haveΣ1∈ζ.s.t.x∈I C(I)≥1. The value of a fractional-coloring C isΣ1∈ζ.s.t.x∈I C(I). The fractional chromatic numberλ_f(G) of G is the infimum of the values of fractionalcoloring of G.Frational-coloring of a graph G has an equivalent definition.λ_f(G)=(?)λb(G)／b=(?),χ_b(G) is the b-fold chromatic number of G. Assigns to each vetex of G a set of b colors, and adjacent vertices receive disjoint sets of colors, if all colors are draw from a palette of a colors, We say that G is a: b-colorable. We sometimes refer to such a coloring as an a: b-coloring. The least a for which G has a: b-coloring is the b-fold chromatic number of G.χ_b(G)=min{a| G has a: b-coloring}.Definition 1 G is fractional colour-critical grpah ifχf(H)＜χf(G) for every proper subgraph H of G.Theorem 2. 1. 1 Vertex cut of fractional colour-critical graphs is not clique.Corollary 2. 1. 2 Every fractional colour-critical graph is 2-connected.Theorem 2. 1. 3 suppose G is a graph.v is a vertex of G and X(?)N_G(v)is a clique of G contained in the neighbonrhood of v. Let G′be obtained from G by deleting all the edges{vx: x∈X}. thenχf(G′)≥χf(C)-1.Corollary 2. 1. 4 suppose G is a graph. for any edge e of G, thenχf(G－e)≥χf(G)－1.Theorem 2. 1. 5 suppose G is a graph. for any vertex v of G. thenχf(G-v)≥χf(G)-1.Theorem 2. 1. 6 If G is aχf(G)-fractional colour-critical graph, thenδ(G)≥「χf(G)」-2.Corollary 2. 1. 7 For every graph G. there are at least「χf(G)」-1 vertexs whose degrees are no less than「χf(G)」-2.Theorem 2. 1. 8 G. H is Graph with G≠K_n. H≠K_n. n≥1.then G V H is not fractional colour-eritical graph.Theorem 2. 1. 9 If u, v are vertices of G which is fractional colour-critical graph.then N(u)is not subset of N(u). Theorem 2. 1. 10 If G is an n-critical graph andχf(G)=χ(G), for any element t of V(G)∪E(G), thenχf(G-t)=χf(G)-1.Theorem 2. 1. 11 If G is an n-critical graph andχ(G)-χf(G)≤1, then G is fractional colour-critical graph.Theorem 2. 1. 12 G is fractional colour-critical graph andχ(G)=χf(G), Ifχf(G)-χf(G-t)＜1, for any element t of V(G)∪E(G), then G is critical graph.Definition 2^[8] Suppose G₁, G₂ are graphs and e=x₁y₁, e^′=x₂y₂ are edges of G, G′respectively. The Hajos sum of G₁ and G₂(with respect to e and e^′) is the graph obtained from the disjoint union of G₁ and G₂ by deleting e and e^′. identifying x₁ and x₂, and adding an edge that connects y₁ and y₂.Theorem 2. 2. 1 Hajos sumG=(G₁, x₁y₁)+(G₂, x₂y₂), then max{χf(G₁),χf(G₂)}-1≤χf(G)≤max{λf(G₁),λf(G₂)}.Note: upper bound and lower bound can not improve.Corollary 2. 2. 2 Hajos sumG=(G₁, x₁y₁)+(G₂, x₂y₂), if the graph whose fractional chromatic number is the larger is not fractional colour-critical graph, thenχf(G)=max{χf(G₁),λf(G₂)}.Theorem 2. 2. 3 Hajos sumG=(K_n, u₁u₂)+(K_m. u₁u₂), identify u₁, u₁ into a vertex u₀. If m=n. thenχf(G)=n-1/2, otherwiseλf(G)=max{χ(K_n).λ(K_m)}-1.Theorem 2. 2. 4 Hajos sumG=(K_n, u₁ u₂)+(K_n^′. u₁ u₂) is fractional colour-critical graph. where identify u₁. u₁ into a vertex u₀. adding an edge that connets u₂ and u₂.Definition 3^[9] Given 2k+1(k≥1) graphs G₀, G₁, G₂,…, G_2k. For i=0, 1, 2,…, 2k. let e_i=x_iy_i be an edge of G_i. Let C_2k+1=(c₀, c₁,…, c_2k be a cycle of length 2k+1, Construct a new graph from the disjoint union of G₀, G₁, G₂,…, G_2k, C_2k+1 as follows: (1): delete the edges e_i, for i=0, 1, 2,…, 2k,(2): identify all the x_i into a single vertex and name it x,(3): identify y_i and c_i for i=0, 1, 2,…, 2k.We shall denote the resulting graph by S₁(G₀, e₀, G₁, e₁, G₂, e₂,…, G_2k, e_2k), simply by S₁.Theorem 2. 2. 5 Graph S₁(G₀, e₀, G₁, e₁, G₂, e₂,…, G_m-1, e_m-1), simply byS₁, ifmax{χf(G₀),χf(G₁),…,χf(G_m-1)}≥4, thenχf(G)－1≤χf(S₁)≤χf(G), whereχf(G)=max{χf(G₀),χf(G₁),χf(G₂),…,χf(G_m-1)}.Note: upper bound and lower bound can not improve.Corollary 2. 2. 6 If the graph whose fractional chromatic number is the the largest is not fractional colour-critical graph. thenχf(S₁)=max{χf(G_i).: i=0, 1,…, m-1}.Given m(m≥3) graphs. G_i=N_n, i=1, 2,…, m-1. then S₁(G₀, e₀, G₁, e₁, G₂, e₂,…, G_m-1, e_m-1)=S₁(K_n, e₀, K_n, e₁, K_n, e₂,…, K_m-1, e_m-1), simply by S₁^′.Theorem 2. 2. 7 Graph S₁(K_n, e₁, K_n, e₂, K_n, e₃,…, K_m, e_m). simply by S₁^′. thenχf(S₁^′)=χf(K_n)-1／χf(C_m).Given m(m≥3)graphs. G_i is odd cycle Cⁱ for i=0, 1, 2,…, m-1. then S₁(G₀, e₀, G₁, e₁, G₂, e₂,…, G_m-1, e_m-1)=S₁(C⁰, e₀. C¹, e₁, C², e₂,…, C^m-1, e_m-1), simply by S_t^″.Theorem 2. 2. 8 Graph S₁^″(C¹, e₁, C², e₂. C³. e₃.…, C^m, e_m). simply by S₁^″. thenχf(S₁^″)=3-1／χf(C_m).Definition 4^[9] Given n graphs G₀, G₁, G₂,…, G_n-1, For i=0, 1, 2,…, n-1. let e_i=x_iy_i be an edge of G_i. Construct a new graph from the disjoint union of G₀, G₁, G₂,…, G_n-1 as follows:(1): delete the edges e_i, for i=0, 1, 2,…, n-1.(2): identify y_i with x_i+1, for i=0, 1, 2,…, n-1.(3): add edges to connect x_i and x_i+2 for i=0, 1, 2,…, n-1 . (4): add a vertex u and connect u to x_i for i=0, 1, 2,…, n-1.We shall denote the resulting graph by S₂(G₀, e₀, G₁, e₁, G₂, e₂,…, G_n-1, e_n-1, simply by S₂.Theorem 2. 2. 9 Graph S₂(G₀, e₀, G₁, e₁, G₂, e₂,…G_2k, e_2k), simply byS₂. then max{χf(G_i): i=1, 2,…, n-1}-1≤χf(S₂)≤max{χf(G_i): i=1, 2,…, n-1}+1.Note: lower bound can not improve.Definition 5^[10] Suppose k≥3, G₀, G₁, G₂,…, G_4k-1 are graphs and for i=0, 1, 2,…, 4k-1, e_i=xiyi is an edge of G_i. Let C_2k=(c₀, c₁,…, C_2k-1) be a cycle of length 2k. Construct a new graph from the disjoint union of G₀. G₁, G₂,…, G_4k-1 as follows:(1): delete the edges e_i from G_i, for i=0, 1, 2,…, 4k-1.(2): identify x₀, x₁,…, x_2k-1 into a single vertex x, and for i=0, 1, 2,…, 2K-1. identify y_i with c_i.(3): for i=0, 1, 2,…, 4k-1. identify x_i with e_i-2k and y_i with c_i-2k+3, where the addition is modulo 2k.We shall denote the resulting graph by S₃(G₀, e₀, G₁, e₁, G₂, e₂,…, G_4k-1, e_4k-1). simply by S₃.Theorem 2. 2. 10 Graph S₃(G₀, e₀, G₁, e₁, G₂, e₂,…, G_4k-1, e_4k-1), simple byS₃, if max{λf(G_i): i=0, 1, 2.…, 4k-1}≥7, then max{χf(G_i): i=1, 2,…, 4k-1}-1≤χf(S₃)≤max{χf(G_i): i=1, 2,…, 4k-1}.Note: upper bound and lower bound can not improve.Corollary 2. 2. 11 If the graph whoso fractional chromatic number is the largest is not fractional colour-critical graph. thenλf(S₃)=max{λf(G_i): i=0, 1,…, 4k-1}.Definition 6^[9] Given 7 graphs G₁. G₂.…, G₇. Let P₅ be the path with five vertices P₁, P₂,…. P₅. For i=1, 2,…, 7. let e_i=x_iy_i be an edge of G_i. Construct a new graph from the disjoint union of G₁, G₂,…, G₇ and P₅ as follows:(1): delete the edges e_i. for i=1, 2,…, 7, (2): identify y1, y2, y3, y4, y5, into a single vertex, and name it y, and identify x_i with p_i for i=1, 2,…, 5, and name it x_i,(3): identify x₆ with x₂, y₆ with x₅, x₇ with x₁, y₇ with x₄.We shall denote the resulting graph by S₄(G₁, e₁, G₂, e₂,…, G₇, e₇), simply by S₄.Theorem 2. 2. 12 Graph S₄(G₁, e₁, G₂, e₂, G₃, e₃,…, G₇, e₇), simply byS₄, if max{χf(G_i): i=1, 2,…, 7}≥6, then max{χf(G_i): i=1, 2,…, 7}-1≤χ_S4≤max{χf(G_i): i=1, 2,…, 7}.Note: upper bound and lower bound can not improve.Corollary 2. 2. 13 If the graph whose fractional chromatic number is the largest is not fractional colour-critical graph, thenχf(S₄)=max{χf(G_i): i=1, 2,…, 7}.Definition 7 Distance join graph GV_DG′defined as follows: vertex set is V(G)∪V(G′), edge set is E(G)∪E(G′)∪{(i′, j″)|d(i″, j″) = k, k∈D, i″corre-spond with i′∈V(G)}, where G′is the copy of graph G, V(C)= {1′, 2′.…, n′}. V(G′)={1″, 2″,…. n″}, and D=N∪{0}.Lemma 2. 3. 1 Any independent setâ… of distance join graph GV_DG′. there is an independent setⅠ′in G or G′. such that(?)f(i)=(?) f′(i′)(=(?)f′(i″)), where f′is optimal fractional clique of G and G′, the fractional clique f be defined by f′as follows:Theorem 2. 3. 2 Distance join graph GV_DG′. D={0. 1}, thenχf(GV_DG′)=2λf(G).Theorem 2. 3. 3 If G is fractional colour-critical graph, then GV_DG′={0, 1} is fractional colour-critical graph. Theorem 2.3.4 C_nV_DC′_n, D={k} is distance join graph, thenNote: Ifα(G)=2m-k+1, then Xf(C_nV_DC′_n)=(4m+2)／(2m-k+1).Theorem 2.3.5 C_nV_DC′_n,D={0, k} is distance join graph, thenNote: Ifα(G)=m, then Xf(C_nV_DC′_n)=2xf(C_n). Ifα(G)=2m-k+1, then Xf(C_nV_DC′_n)=(4m+2)／(2m-k+1).Theorem 2.3.6 C_nV_DC′_n, D={k, k+1}, k≤m-1 is distance join graph. then Xf(C_nV_DC′_n)≤2Xf(C_n).Note: Ifα(G)=m. then Xf(C_nV_DC′_n)=2Xf(C_n).Theorem 2.3.7 C_nV_DC′_n, D={k, k+2,...,k+i,}is distance join graph, i is even and k+i≤m, thenNote: Ifα(G)=2m-(k+i)-1, then Xf(C_nV_DC′_n)=(4m+2)／(2m-(k+i)-1).Definition 8 Let G be a graph with vertex set and edge set E⁰. Given an integer m≥1, the m-Mycielskian of G, denoted byμ_m(G), is the graph with vertex set V⁰∪V¹âˆªV²âˆªâ€¦âˆªV^m∪{u}. where is the ith distinct copy of V⁰ for i=1.2….m.and edge setWe defineμ0(G) to be the graph obtained from G by adding a universal vertex u. The Mycielskian of G. denoted byμ(G), was simplyμ1 (G). is given in [12] by Claude Tardif. in this article, we give another proof about supremum of Xf(μ_m(G)).Theorem 2.4.1 For any graph G with Xf(G)=a/b and exists a a: b-colouring, then Xf(μ_m(G))≤a／b+b^m／B′, where B′=b^m+b^m-1(a-b)…+b(a-b)^m-1+(a-b)^m, and integers m≥0.Theorem 2.4.2 Graphμ_m(K_n) with integers m≥1, n≥3 is fractional colour-critical graph.Definition 9 Let G be a graph with one universal vertex, and G′is the copy of G. We define G(?)G′as follows: vertex set is V(G)∪V(G′), edge set is E(G)∪E(G′)∪{u′v_i:u′∈V(G′) is universal vertex of G′. v_i∈V(G)}∪{uv′_i:is universal vertex of G, v′_i∈V(G′)}.Theorem 2.4.3 Graph G(?)G′, then Xf(G(?)G′)=Xf(G)+1.