Two Kinds Of Graph Coloring Problems Related To The Channel Assignment

The coloring problem of graphs is one of primary fields in the study of graph theories. The coloring problem plays an important role in the combinatorial mathmatics and our living.As the development of science,the classics colorings cannot meet the requirement, and some new colorings are proposed.A(proper) k-coloring of graph G is an assignment of one of k colors to each vertex in such a way that adjacent vertices have distinct colors.Define the chromatic number of G asχ(G)=min {k｜graph G has k-colorings}.Similar,a(proper) k-edge-coloring of graph G is an assignment of one of k colors to each edge so that no two adjacent edges have the same color.the edge-chromatic number of G asχ′(G)=min{k｜graph G has kedge -colorings}.Griggs and Yeh introduced L(2,1)-labellings in.Its natural generalization L(p,1)-labelling of a graph is an integer assignment L to the vertex set V(G) such that:(1)｜L(u) - L(v)｜≥p,if d_G(u,v) = 1;(2)｜L(u) - L(v)｜≥1,if d_G(u,v) = 2.L(p,1)-labelling of a graph plays an important role in the frequency assignment.Whi -ttlesey et al.in studied L(2,1)-labellings of first subdivision of a graph G.The first subdivision of a graph G is the graph s₁(G) obtained from G by inserting one vertex along each edge of G.An L(p,1)-labelling of s₁(G) corresponds to an assignment of integers to V(G)∪E(G) such that: (1)any two adjacent vertices of G receive distinct integers;(2)any two adjacent edges of G receive distinct integers;(3)a vertex and edge incident receive integers that differ by at least p in absolute value.We call such an assignment a(p,1)-total labelling of G.The span of a(p,1)-total labelling is the maximum difference between two labels. The minimum span of a(p,1)-total labelling of G is called the(p,1)-total number and denoted byλ_p^T(G).Now the study of the(p,1)-total labelling is not enough.In the paper,the triviality lower and upper bounds are given and the(p,1)-total labelling conjecture:λ_p^T(G)≤△(G) + 2p-1.The packing coloring is presented with the application to frequency assignments recently.The packing coloring is a variation of the coloring,and a partition of the graph vertices.All of the vertices should be partitionded into the packings X_i with pairwise diffent widths,so that in the same packing X_i the vertices must be pairse at distance more than i and be colored with the same coloring.The different packings must be colored with different colorings.The packing chromatic numberχ_ρ(G) = min{k｜graph G has k-packing coloring}.The first chapter of this paper gives the basic conceps,terminologies and symboles which are used in this paper and a brief introduction about the development of the graph coloring.In the second chapter,we study the(p,1)-total labelling of graphs such as outerplanar graph,bipartite graph,regular graph,Halin graph.In the third chapter,we study the packing coloring of graph.The best possible upper bounds on the packing chromatic number of the bipartite graph and Mycielskian-graph are given.Finally the packing chromatic numbers of some paticular graphs are given.In this paper we have the following theorems:Theorem 2.1.4 Let G be a 2-connected outerplanar and triangle -free graph withâ–³(G) =3,if p≥3,thenλ_p^T(G) =p+3. Theorem 2.2.2 Let G be a bipartite graph withâ–³(G)=3,not regulax,if G contains a vertex with maximum degree which is adjacent to two vertices with maximum degree,thenλ₂^T(G) = 5.Theorem 2.2.4 Let G be a bipartite graph withâ–³(G) = 4,not regular,if the induced graph G_â–³of the vertices with maximum degree contains K_1,3,thenλ₂^T(G) = 6.Theorem 2.3.1 Let G be aâ–³-regular graph,if p＞χ(G) +χ′(G) - 2,andχ′(G) =â–³(G),thenλ_p^T(G) =χ(G) +χ′(G) + p- 2.Theorem 2.3.2 If G is a 3-regulax graph with 1-factor,thenλ_p^T(G)≤p + 5.Theorem 2.3.3 Let G be a 3-regular graph,ifχ(G) = 3,p＞3,thenλ_p^T(G)≥p+4.Definition 2.4.1 For a 3-connected plane graph G(V,E,F),if all edges on the boundary of one face f₀ of the face set F are removed,it becomes a tree,and the degree of each vertex of V(f₀) is three,then graph G is called a Halin graph,the vertices on V(f₀) are called exterior vertices of G,and the others interior vertices of G.Theorem 2.4.3 If G is a 3-regular Halin graph,then 5≤λ₂^T(G)≤6.Theorem 2.4.5 If G is a Halin graph withâ–³(G) = 4,thenλ₂^T(G)≤6.Definition 2.5.1 Let G be a connected graph,with V(G) = {v₁,v₂,...,v_n}.Let G′be a copy of G with V(G′)= {v₁^′,v₂^′,...,v_n^′}.A new graph D(G) is defined as followings:V(D(G))= V(G)∪V(G′),andE(D(G))= E(G)∪E(G′)∪{v₁v₁^′,v₂v₂^′…, v_nv_n^′,},We call it double graph D(G).Theorem 2.5.1 Let Cn be a cycle,thenλ₂^T(D(C_n)) =5.Theorem 2.5.2 Let G be a connected graph,withλ₂^T(G)=â–³+ 4,D(G) be the double graph gained by G,thenλ₂^T(D(G))≤λ₂^T(G) + 1. Theorem 3.1.1 Let G_m,n be a bipartite graph,thenχ_ρ(G_m,n)≤min{m,n} + 1,and this upper bound is best possible.Mycielskian-graph of simple graph plays an important role in the study of the critical property of graph coloring.Here we study the packing coloring of Mycielskian-graphTheorem 3.1.4 Let G be a simple graph,and｜G｜= n.M(G) be the Mycielskian-graph of G,thenχ_ρ(M(G))≤n + 2.and this upper bound is best possible.In addition,we also study the the packing coloring of some particular graphs.