Some Topics On Colorlng Problems Of Graphs

Let G=(V, E) be a graph with the set of vertices V and the set of edges E, we denote its maximum degree and minimum degree byâ–³and δ, respectively. If G is a plane graph, we denote its face set by F. If one can use k colors to color all elements in V∪E such that any two adjacent or incident elements receive distinct colors, then G is said to be k-totally-colorable. We use χ"(G) to denote the total-number, the minimum integer such that G has a k-total-coloring. A mapping φ:Vâ†'{1,…,k} is called a k-coloring of G if φ(u)≠6(v) whenever uv∈E. If G has a k-coloring, then G is called k-colorable. We use χ(G) to denote the vertex-number, the minimum integer such that G has a k-coloring. Now assign each vertex v a coloring set L(v), then L={L(v)|v∈V} is said to be a color list. If for any vertex v∈G, we can choose a color φ(v) from the corresponding color list L(v), such that(?)uv∈E(G),φ(u)≠φ(v), then G is said to be L-colorable. If for any color list L such that|L(v)|≥k, G is L-colorable, then G is said to be k-list-colorable, or k-choosable. We use ch(G) to denote the chromatic number of G, the minimum integer k such that G is k-choosable. 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 a union of vertex-disjoint paths. The linear chromatic number lc(G) of a graph G is the minimum integer k such that G has a linear k-coloring.Based on the previous work, this thesis studies these three coloring problems of graphs. This thesis consists of four chapters. In the first chapter, we introduce some problems, backgrounds and the definitions of total coloring,3-list coloring and linear coloringIn the second chapter, we mainly deal with the total coloring problem of plane graph. About total coloring of graphs, we have the following conjecture (Total Col-oring Conjecture):For any graph G,χ"(G)≤△(G)+2. Conjecture was posed independently by Vizing and Behzad, we call it TCC for short. It is interesting that we notice many plane graphs are proved to beâ–³(G)+1-total-colorable. In this chapter, we investigate the total coloring of plane graphs with maximum degree at least6with neither chordal5-cycle nor chordal6-cycle.In the third chapter, we mainly deal with the3-list coloring problem of plane graph. About3-choosable, it is based on3-colorable. Steinberge Conjecture pointed that plane graphs without cycles of length4or5are3-colorable. A natural problem is that are plane graphs without cycles of length4or53-choosable? Montassier gave an example of plane graphs without cycles of length4or5but not3-choosable. Montassier proposed this conjecture:Plane graphs without cycles of length4,5.6are3-choosable. In this chapter, we get every plane graph without4,5,8or10-cycle is3-choosable and every plane graph without4,6,9or10-cycle is3-choosable.In the fourth chapter, we deal with linear coloring of graphs. About linear color-ing, obviously, lc(G)≥[â–³/2]+1. Cranston and Yu conjectured:For any graph with mad(G)<3, lc(G)≤[â–³/2]+2. In this chapter, we investigate linear coloring of graphs with mad(G)<2.8.