On Some Coloring Problems Of Graphs

Graph theory is an important branch of mathematics,in which graph coloring theory plays an important role in graph theory.The aim of this thesis is to discuss some coloring problems of graphs,such as f-coloring of random graphs,coloring of r-uniform C-hypergraphs and weakly edge-face coloring of series parallel graphs.Let G=(V(G),E(G))be a graph,where V(G)is the vertex set of G,and E(G)is the edge set of G.Define an integer-valuod function f on such that f(v)>0 for every v?V(G).An f-coloring c of G is an edge coloring,so that each color class can appear at most f(v)times on every vertex v.The minimum number of colors needed for f-coloring of G is defined to be the f-chromatic index of G and it is denoted by ?'f(G).Hakimi and Kariv proved that for a simple graph,?f-(G)??f'(G)??f(G)1.This shows:similar to the ordinary edge-coloring of a graph,f-coloring of a graph can also be divided into two classes.If ?f'(G)=?f(G),the graph G is called f-class 1,otherwise it is called f-class 2.First of all,based on the related conclusions of f-coloring,we study the clas-sification of f-coloring of random graphs.We are concerned about whether there exists a function g about ? such that if f(v)=g(?)for all v?V(G),then random graphs G(n,1/2)is f-class 1,and we generalize the above result to random graphs G(n,p).So we get some results about the classification of f-coloring of random graphs.Secondly,we study the coloring problem of r-uniform C-hypergraphs.A mixed hypergraph is a triple H=(X,C,D),where X is called the vertex set,C is the family of subsets of X called C-edges,and D is the family of subsets of X called D-edges.A mixed hypergraph with C=(?),denoted by H=(X,D),is called D-hypergraph,and a hypergraph with D=(?),denoted by H is called a C-hypergraph.Let H=(X,C,D)be a mixed hypergraph,r is a positive integer not less than 2.For an arbitrary C-edge and D-edge,if we have |C|=r,|D|=r,then the mixed hypergraph H is called r-uniform mixed hypergraph.In particular,if D=(?),the mixed hypergraph H is called r-uniform mixed C-hypergraph.In 2002,Vitaly Voloshin posed an open problem concerning the maximum number of hyperedges of an r-uniform C-hypergraph H with the condition ?(H)?k.In this paper,we obtain the upper bound of the maximum number of hyperedges of an r-uniform C-hypergraph with the condition ?(H)=k.Then,we study weakly edge-face coloring of series parallel graphs.In 2016,based on the definition of edge-face coloring,Fabrici et.al gave the concept of weakly edge-face coloring of planar graphs.At the same time,Fabrici et al proved that every loopless,bridgeless and connected plane graph is weakly edge-face 6-colorable,and gave the following conjecture:every loopless,bridgeless and con-nected plane graph is weakly edge-face 5-colorable.Until now,only some special plane graphs such as plane triangulations,outerplanar graphs and Halin graphs are proved to satisfy the conjecture.In this paper,we obtain the following result:if G is a series parallel graph,then G is weakly edge-face 5-colorable.The thesis consists of five chapters.In Chapter 1,we introduce the back-ground and significance of the classification of.f-coloring of graphs,C-hypergraphs and weakly edge-face coloring,give some basic concepts and symbols involved in this thesis,expound the research progress of related fields and list our main conclu-sions in this paper.In Chapter 2,we mainly study the classification of f-coloring of random graphs.In Chapter 3,we study the coloring problem of r-uniform C-hypergraphs,and solve the open problem posed by Voloshin.In Chapter 4,we study weakly edge-face coloring of series parallel graphs,and prove that the con-jecture proposed by Fabrici et.al is also true for series parallel graphs.In Chapter 5,we indicated some problems for further research.