The Problem On K-Fold Coloring Of Graphs

The coloring of graphs, one of the most interesting and rapidly growing areas of researches in graph theory, has great theoretical value and applied background. In 1976, Stahl introduced k-fold coloring based on proper vertex coloring. Let G = (V, E) be a finite, simple and undirected graph with the set of vertices V and the set of edges E. A k-fold n-coloring of a graph G is an assignment of k distinct colors to each vertex of G from n colors, such that adjacent vertices receive no colors in common. If G has a k-fold n-coloring, we can say G is k-fold n-colorable. Denote the k-th chromatic number of G byχκ(G),χκ(G) = min{n : G is k-fold n-colorable}. Clearlyχι(G) is the ordinary chromatic number of G, i.e.,χι(G) =χ(G), whereχ(G) is the chromatic number of G. A great number of problems about this topic have not been solved so far. This dissertation mainly discusses the k-fold coloring of planar graphs and some special graphs.This dissertation consists of five chapters. Chapter 1 is an introduction to the background of the research presented in the dissertation.In Chapter 2 and Chapter 3, this dissertation studies k-fold coloring problems of planar graphs. The main results obtained in this dissertation may be summarized as follows:(1) Let G be an outerplanar graph, then G is k-fold 2k-colorable or k-foldχκ(C~*)- colorable(C~* is the shortest odd cycle).(2) Let G be a planar graph with odd girth at least 10k - 9(k≥3), then G is k-fold (2k +1)-colorable.(3) Let k be odd, G be a planar graph with odd girth at least 5k - 2 (k≥3), then G is k-fold (2k + 2)-colorable.In Chapter 4, we calculate the k-th chromatic number of some Mycielskian graphs.In Chapter 5, we introduce some further problems on k-fold coloring of planar graphs.