Some Topics On Coloring Problems Of Graphs

Graph theory is a backbone branch of discrete mathematics. It has im-portant theoretical and practical significance and is widely used in manage-ment science, computer science, communications engineering and other fields. The study of graph theory started over two hundreds years ago. The earliest known paper is due to Eulcr (1736) about the seven bridges of Konigsbcrg. Since1950s, with the rapid development of the computer science, graph the-ory has developed very fast and numerous results on graph theory appeared in a rash. The Four-Color Conjecture, the origin of graph coloring theory, has always led the way in graph theory. And graph coloring has become a very important branch in graph theory. The aim of this thesis is to discuss some colorings of graphs, including equitable colorings and equitable choos-ability, list edge and list total colorings and neighbor sum distinguishing edge colorings.In this thesis, all graphs considered arc simple graphs. For a graph G, let V(G), E(G), δ(G) and△(G) denote its vertex set, edge set, minimum degree and maximum degree, respectively. For each v∈V(G), we use dG(x) to denote the number of edges incident to v in G and write it down for d(v) in brief. Let S be a set,|S|denotes the number of element in S. For each real number x,[x],[x]are the least integer not less than x and the largest integer not larger than x, respectively. We use ad(G) to denote the average degree of G, i.c. ad(G)=∑v∈V(G)d(v)/|V(G)|.Let mad(G) denote the maximum value of the average degrees of all the subgraphs in G and call it maximum average degree. For each v∈V(G), if d(v)=k, then G is a k-regular graph. If any subgraph of G has a vertex v such that d(v)≤3, then G is3-dcgcncratc. A cycle of length k is called k-cyclc, if there exist an edge xy∈E(G)-E(C) and x, y∈V(C), the cycle C is called k-cyclc with chord. A3-cyclc is also called a triangle. The girth of a planar graph is the length of the smallest cycle in it, denotes the girth of a graph G by g(G).A graph G is said to be planar, if it can be drawn in a plane so that its edges intersect only at their ends. Such a drawing of a planar graph G is called a planar embedding of G. For convenience, we refer to a planar embedding of a planar graph as a plane graph. A plane graph G partitions the plane into a number of connected regions, which we called the faces of G. By F(G), we denote the set of faces of G.In the following, we simply introduce some concepts on the topics of colorings discussed in this thesis. The equitable colorings of graphs is a special vertex coloring. A graph G is said to be equitably k-colorablc if the vertex set V(G) can be partitioned into k independent subsets V1, V2,…, Vk such that||Vi|-|Vj||≤1(1≤i,j≤k). The equitable chromatic number of G, denoted by Xe(G), is the smallest integer k such that G is equitably k-colorablc. The equitable chromatic threshold of G, denoted by Xe*(G), is the smallest integer k such that G is equitably l-colorable for all l> k. For a graph G and a list assignment L assigned to each vertex v∈V(G) a set L(v) of acceptable colors, a L-coloring of G is a proper vertex coloring c such that for every v∈V(G), c(v)∈L(v). A list assignment L for G is k-uniform if|L(v)|=k for all v∈V(G). A graph G is equitably k-choosable if, for any k-uniform list assignment L, G is L-colorablc and each color appears on at most [|V(G)|/k] vertices.The list edge and list total colorings arc generalization on edge colorings and total colorings. The mapping L is said to be a total assignment for a graph G if it assigns a list L(x) of possible colors to each clement x∈V(G) U E(G). If G has a proper total coloring φ(x)∈L(x) for all x∈V(G) U E(G), then we say that G is total L-colorablc. If We say that G is total k-choosablc if it is total L-colorablc for every total assignment L satisfying|L(x)|=k for all x∈V(G)U E(G). The list total coloring number χ"i(G) of G is the smallest integer k such that G is total k-choosable. The list edge coloring number χ'i(G) of G is defined similarly in terms of coloring edges alone, we omit it.The neighbor sum distinguishing edge coloring is a special edge coloring. A proper [k]-edge coloring of a graph G is a proper edge coloring of G using colors of the set [k]={1,2,…, k}. A neighbor sum distinguishing [k]-edge coloring of G is a proper [k]-edge coloring of G such that for each edge uv∈E(G), the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. By ndi∑(G), we denote the smallest value k in such a coloring of G.This thesis is concerned with some topics on colorings of graphs. We mainly discuss equitable colorings, equitable choosability, list edge and list total colorings, neighbor sum distinguishing edge colorings. We have con-structed our work in four chapters.In Chapter1, we give some basic definitions and notations. Then we present definitions, research and development of colorings which we discussed in this thesis. At last, we outline the main results of this thesis.In Chapter2, we discuss equitable colorings and equitable choosabil-ity. We considered planar graphs and improved some results of Bu et al.[20,57,68,85,91,92] so that further confirmed the conjectures on equi-table colorings. In addition, we studied equitable colorings and equitable choosability of graphs with bounded maximum average degree.In Chapter3, we consider list edge and list total colorings of planar graphs. We checked the conjecture on list edge and list total colorings for some special planar graphs.In Chapter4, we discuss neighbor sum distinguishing edge colorings. First we gave an upper bounds on neighbor sum distinguishing edge colorings number of planar graphs. In addition, we generalized the result of Wang et al.[72] and further confirmed the conjecture on neighbor sum distinguishing edge coloring for graphs with lower maximum average degree.