Vertex Distinguishing Colorings, List Colorings And Linear Colorings Of Graphs

The study of graph theory started over two hundreds years ago. The earliest known paper is due to Euler (1736) about the seven bridges of Konigsberg. Since 1960s, graph theory has developed very fast and numerous results on graph theory sprung forth. For more than one hundred years, the development of graph theory was inspired and guided mainly by the Four-Colour Conjecture. So graph color-ing theory has a central position in graph theory. Graph coloring has interesting real-life applications in optimization, computer science and network design, such as file transfers in a computer network, computation of Hessians matrix and so on. The aim of this thesis is to discuss some colorings of graphs, such as vertex distinguishing edge coloring, adjacent vertex distinguishing edge coloring, adjacent vertex distinguishing total coloring, list edge coloring, list total coloring and linear coloring.In the thesis, all graphs considered are finite and simple. Let G be a graph with vertex set V(G) and edge set E(G). A proper k-total-coloring of a graph G is a coloring of V(G)∪E(G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic numberχ″(G) is the smallest integer k such that G has a k-total-coloring. The chromatic numberχ(G) of G and the edge chromatic number (or chromatic index)χ′(G) of G are defined similarly in terms of coloring vertices alone or edges alone, respectively.The following three colorings are all related to irregular coloring. A proper edge coloring is called vertex-distinguishing if every two distinct vertices are inci-dent to different sets of colored edges. The minimum number of colors required for a vertex distinguishing proper edge coloring of a simple graph G, denoted byχ′vd(G), is called the vde-chromatic number of G. A k-adjacent vertex distinguish-ing edge coloring or a k-avd-coloring of a graph G is a proper k-edge coloring of G such that no pair of adjacent vertices meets the same set of colors. The avd-chromatic number, denoted byχ′a(G),is the minimum number of colors needed in an avd-coloring of G. A k-adjacent vertex distinguishing total coloring or a k-adt-coloring is a proper k-total coloring of G such that no pair of adjacent vertices meets the same set of colors. The adt-chromatic number of G, denoted byχ″a(G), is the minimum number of colors needed in an adt-coloring. Several upper bounds on these colorings are given in thesis.Another topic discussed in this thesis is list coloring. We say that a mapping L is an edge assignment for the graph G if it assigns a list L(e) of possible colors to each edge e∈E(G). If G has a proper edge-coloringφsuch thatφ(e)∈L(e) for every edge e∈E(G), then we say that G is edge-L-colorable orφis an edge-L-coloring of G. The graph G is edge-k-choosable if it is edge-L-colorable for every edge assignment L satisfying丨L(e)丨≥k for each edge e∈E(G). The list edge chromatic number of G, denoted byχ′l(G), is the smallest integer k such that G is edge-k-choosable. The list chromatic numberχl(G) and the list total chromatic numberχ″l(G) of G can be defined similarly in terms of coloring vertices alone, or both vertices and edges, respectively. It follows directly from the definition that x′(G)≥χ′(G)≥Δandχ″(G)≥χ″(G)≥Δ+1. We mainly discussed list colorings on planar graphs in this thesis.A linear k-coloring of a graph G is a proper k-coloring of G such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number k such that G has a linear k-coloring. Our aim is to find lower bounds on linear colorings of graphs.This thesis is concerned with some topics on colorings of graphs. More specif-ically, our aim is to discuss vertex distinguishing edge coloring, adjacent vertex distinguishing edge coloring, adjacent vertex distinguishing total coloring, list edge coloring, list total coloring and linear coloring of graphs. We have constructed our work in six chapters. A short but relatively complete introduction is given in Chapter 1. First, we give some basic definitions and notations. Then we describe some definitions and history of the colorings which we consider in this thesis. At last, we outline the main results of this thesis.In Chapter 2, we consider vertex distinguishing edge colorings of graphs. We improved a result of Bazgan et al. [13] by replacing the conditionδ(G)>n/3 byσ2(G)≥(2n)/3. The method is that we first give a subgraph of G a semi-vde-coloring, and then we transform it to G using several extra colorings.In Chapter 3, we discuss adjacent vertex distinguishing edge colorings of graphs. First, we give upper bounds of the avd-chromatic number of graphs with circumference no more than 4. Then, we consider several 3-colorable graphs, and also give upped bounds of the avd-chromatic number of these graphs.In Chapter 4, we we discuss adjacent vertex distinguishing total colorings of graphs with circumference no more than 4, and give an upper bound of the adt-chromatic number of these graphs.In Chapter 5, we consider total colorings, list edge colorings and list total colorings of planar graphs. We give the exact value of total chromatic number of planar graphs withΔ≥7, the exact value of the list edge and list total chromatic number of planar graphs with some restrictions onΔ, the upper bounds of the list edge and list total chromatic number of planar graphs without triangles at small distance.In Chapter 6, we consider linear colorings of planar graphs. We give an upper bound on the linear chromatic number of planar graphs and two others of planar graphs with girth restrictions.