Study On Some Properties Of Crictical Graphs And Incidence Coloring Of Graphs

An edge coloring of loopless graph G is a mappingπfrom E to a color set C, such that any two adjacent edges of G have different images. If |C|=k, then we callπis a k-edge coloring of G. The edge chromatic numberχ'(G), is the minimum k for which G has a k-edge coloring. Vizing theorem states that for any simple graph G,χ'(G)=△or△+1. A graph G is said to be class one ifχ'(G)=△and class two ifχ'(G)=△+1. A graph G is critical if G is connected, class two andχ'(G-e)＜χ'(G) for any edge e of G. In this dissertation we will discuss some properties of critical graphs with△≥5 according to the definition of critical graph and VAL theorem.A vertex coloring of G is a mappingφfrom V to a color set C, such that any two adjacent vertices have different images. If |C|=k, then we callφis a k-vertex coloring of G. The vertex chromatic numberχ(G) of G is the minimum k for which G has a k-vertex coloring.Let I(G)={(v,e)|v∈V, e∈E, and v is incident with e} be the set of incidences of G. We say two incidences (v,e) and (w,f) are neighborly if and only if one of the following holds: (1)v=w,(2)e=f,(3) vw=e or vw=f. An incidence coloring of graph G is amappingσfrom I(G) to a color set C such that any two neighborly incidences are assigned different colors. Letσ:I(G)→C be an incidence coloring of graph G and |C|=k. Then we say G is k-incidence colorable. The incidence chromatic number, denoted byχ_i(G), is the minimum number k Such that G admits a k-incidence coloring.In this article, we shall present two equivalent definitions of incidence graph according to the definitions and properties of incidence coloring and vertex coloring. Based on this we will discuss some properties of incidence graph and some relationships between incidence coloring and vertex coloring. We shall determine the incidence chromatic number of Meredith's graphs by the method of exchanging colors and enumeration. Using the double inductions and the techniques of exchanging colors we will prove that there exists a (△+2,2) -incidence coloring for series-parallel graphs with△≥4 from the aspect of configuration property. We shall prove that graph G with△=4, mad(G)＜3 exists a (6,2)-incidence coloring by the induction and the techniques of exchanging colors according to the definition of (k,l)-incidence coloring and its configuration property.