Figure F-staining Results

A network topology structure can be indicated by a graph. We can study the structure of network by studying the character of the graph. The theory of studying the character of graphs is the graph theory and the coloring of graphs is one of the important contents. Generally, the coloring of graph is divided into vertex-coloring and edge-coloring. Edge-coloring is divided into proper edge-coloring and f-coloring. The colorings of graphs has applications in many fields, such as wavelength assignment in ASON.All graphs considered in this paper are finite undirected simple graphs. Let G be a graph. Let V(G) be vertex set of G and let E(G) be edge set of G. Let d_G(v) be the degree of the vertex v. It is denoted by d(v) if there is no confusion.Δ(G) is the max degree of G, that is , let f be a function which assigns a positive integer f(v) to each vertex v∈V in G. An f-coloring of G is a coloring of edges such that each vertex v has at most f(v) edges colored with the same color. The minimum number of colors needed to f-color G is called the f-chromatic index of G, and denoted by X'_f(G). If f(v) = 1 for all v∈V(G), the f-coloring problem is reduced to the proper edge-coloring problem.f-colorings have applications in scheduling problems such as the file transfer problem in a computer network [2-4]. The file transfer problem on computer networks is molded as follows. Each computer v has a limited number f(v) of communication ports. For each pair of computer there are a number of files which are transferred between the pair of computers. In such a situation the problem is how to schedule the file transfers so as to minimize the total time for the overall transfer process. The file transfer problem in which each file has the same length is formulated as an f-coloring problem for a graph as follows. Vertices of the graph correspond to nodes of the network, and edges correspond to files to be transferred between the endpoints. Such a graph G describes the file transfer demands. Assume that each computer v has f(v) communication ports, and transferring any file take an equal amount of time. Under these assumptions, the schedule to minimize the total time for overall transfer process corresponds to an f-coloring of G with the minimum number of colors. Note that the edges colored with the same color correspond to files that can be transferred simultaneously.In the proper edge-coloring, one of the most celebrated results is that x'(G) =Δ(G) or x'(G) =Δ(G) + 1 for any graph G, which due to Vizing. In f-coloring, there is similar results. x'_f(G) =Δ_f(G) or x'_f(G) =Δ_f(G) + 1, where . This immediately gives us a simple way of classifying graphs into two classes according to their f-chromatic indices. More precisely, we say that G is of C_j 1 if x'_f(G) =Δ_f(G); and that G is of C_f 2 if x'_f(G) =Δ_f(G) + 1.In this paper,we mainly study f-coloring of graph, and obtain some interesting results. This paper mainly is divided into five chapters.In the first chapter we illuminate background of our study and put forward of the problems, the work we do in the paper and the structure of the paper. The second chapter illuminates the results of the proper edge-coloring and f-coloring. In the third chapter we mainly study the classification of f-coloring and prove some theorems about fan, wheel, series-parallel graph, generalized Petersen graph on f-coloring. In the fourth chapter we study the character of f-critical graphs. The fifth chapter mainly present the following problems for future research.