[R,S,T; F]-Colorings And (P,1)-Total Labellings Of Graphs

Graph theory originated from the30's of18th century. The paper about Konigsberg's seven bridge problem, which was finished in1736by the great math-ematician Euler, is recognized as the first article in graph theory field. Therefore, Euler is also believed to be the ancestor of graph theory research. With the ris-ing and development of graph theory, it is producing a wide range of applications in chemistry, biology, and gradually information theory, control theory, network theory, game theory and computer science. Coloring theory, as one of the most classic problems in graph theory, gets wide attention of the scholars in graph theory field. Begin with the famous;Four Color Conjecture', coloring theory is to grow and mature. In this period, a series of new research points arc produced, such as vetex coloring, edge coloring, total colorng, list coloring, channel coloring, condi-tion coloring and so on. Coloring theory has broad applications in our real life, such as schedule problems, process problems, the classroom assignment problem, site selection, production scheduling problem, channel assignment problem, and so on.The graphs considered in this thesis are connected finite simple graphs. In general, V(G) and E(G) are usually used to denote the vertex set and edge set of G.|V(G)|and|E(G)|arc the numbers of vertices and edges, which also called the order and size of graph G, respectively. A proper k-total coloring of graph G is a coloring of each element in V∪E with k colors, such that no two elements adjacent or incident in G receive the same color. The minimum integer k such that G is k-total colorable is called the total chromatic number and denoted by χ"(G). If only vertices (res. edges) of graph G arc colored, this coloring is called vertex (res. edges) coloring. Obviously, total coloring is a generalization of vertex coloing and edge coloring.Bchzad and Vizing respectively rised the famous 'Total Coloring Conjecture', which is shown as follows:TCC. For any graph G, X"(G)≤Δ+2. Although a large number of literatures on this conjecture have been appeared, this problem has not been fully resolved so far.This thesis mainly discusses two kinds of new coloring problems, which also can be called labelling problems, namely,[r, s, t;f]-coloring and (p,1)-total labeling of graphs. Both of them can be seen as the generalization of total coloring problem.Let f be a function which assigns a positive integer f(v) to each vertex v∈V(G), and let r, s and t be non-ncgative integers. An [r, s, t;f]-coloring of graph G is a mapping c from V(G)∪E(G) to the color set C={0,1,…, k-1} such that|c(vi)-c(vj)|≥r for any two adjacent vertices vi and vj;|c(ei)-c(ej)|≥s and α(vi)≤f(vi) for any edges ei and ej which are incident with vi but colored with different colors, and for all vi∈V(G),α∈C where α(vi) denotes the number of α-edges incident with the vertex vi;|c(ei)-c(vj)|≥t for all pairs of incident vertices and edges. The minimum k such that G has an [r,s,t;f]-coloring is defined as the [r, s, t;f]-chromatic number and denoted by χr,s,t;f(G).[r,s,t]-Coloring was first proposed by Kemnitz and Marangio who studied the properties and used a schedule problem for football match to illustrate its practical application. Kcmnitz and Marangio gave some upper and lower bounds for χr,s,t(G) and a series of results when the parameters r, s, t were taken some particular values.[r, s,t]-Coloring of graphs is a difficult problem, even for some simple graphs as star K1,n complete graph Kn and so on.[r, s, t;f]-Coloring can be regarded as an expansion of [r, s,t]-coloring.Channel assignment problem is essentially an optimization problem on how to distribute radio channel resources in order to achieve the reasonable application. This topic has been studied by research department of AT&T bell laboratories, homeland security, and other agencies. In the channel assignment problem, we need to assign radio frequency (in graph model instead with positive integers) to different radio receivers. In order to avoid the interference, if two radio receivers arc adjacent to each other, then it requires to assign to them channels different by at least2. If two radio receivers arc close but not next to (for example, a radio receiver apart), then the channels assign to them must be different. Inspired by this problem, Roger Yeh proposed L(2,1)-labelling of graphs which was soon generalized to the L(p,q)-labelling format.The incidence graph of some graph G is obtained by replace each edge of G by a path of length2. The(p,1)-total labeling of graphs, defined by Havet, initially originated in the research of L(p,1)-labelling problem for incidence graphs. It can be seen as a generalization of total coloring. A graph G is said to be k-(p,1)-total labelable if and only if there is a function c from V(G)UE(G) to color set C={0,1,…,k} such that(1)|c(u)-c(v)|≥1if uv∈E(G)];(2)|c(e)-c(e')|≥1if edges e and e' are adjacent in G;(3)|c(u)-c(e)|≥p if vertex u is incident to the edge e.The minimum k such that G is k-(p,1)-total labclablc is called the (p,1)-total labelling number and denoted by λpT(G). In this thesis,[r, s, t;f]-coloring and (p,1)-total labelling of graphs arc dis-cussed. The main content and structure arrangement arc shown as follows.Chapter1is the introduction part. The first section of this chapter is a simple instruction of basic concepts and symbols appeared in this thesis. The second section gives a relatively complete introduction for the research background by three aspects, namely total coloring,[r, s, t]-coloring and f-coloring and channel assignment problem. Nextly, the third section gives the basic definition of [r, s, t; f]-coloring and (p,1)-total labelling of graphs, which arc the main research points. Finally, the fourth section lists the main conclusion proved in this thesis.Chapter2basically discusses [r, s, t; f]-coloring of graphs. The first section gives a summarization of the background and also some known results on [r, s, t]-coloring, besides what, also some symbols and notations useful in the proof of our main theorems. The second section is main part of this chapter, where the important results and their proofs arc given. At last, the third section gives several problems for further research.Chapter3basically discusses (p,1)-total labelling of graphs. The first section shows the origin background of (p,1)-total labelling problems and gives the (p,1)-total Labelling Conjecture proposed by Havet and Yu. The second section mainly introduces the research progress about the issue and results have been achieved for some special classes of graphs. The third section firstly gives some concepts and structure lemmas which are useful in the proof of our main theorems, and nextly focuses on the (p,1)-total labelling of graphs related to planar graphs, by which providing new basis for the establishment of (p,1)-Total Labelling Conjecture. At last, the forth section gives several problems for further research.Chapter4mainly focuses on list (p,1)-total labelling of graphs. The first sec-tion gives the definition and a simple introducion on list (p,1)-total labelling. The second section shows a conjecture on the upper bound of parametre Cp,1T(G), which is called Weak List (p,1)-Total Labelling Conjecture. The third section mainly considers some special classes of graphs, such as stars, outcrplanar graphs, graphs embedded in surface with Euler characteristic ε. The proving of the upper bounds on Cp,1T(G) when G is a special graph mentioned above, provides new surpport for the correctness of Weak List (p,1)-Total Labelling Conjecture. At last, the forth section gives several problems for further research.