On The Incidence Coloring Numbers Of Graphs

For the graph G , let I(G) = {(v,e) ∈ V(G)×E(G) lv is incident with e } be the set ofincidences of G . We say that two incidences (v,e) and (w,f) are adjacent, if and only if one of the three following cases holds:(1) v = w; (2) e = f; (3) vw = e or vw = f.An incidence coloring n of G is a mapping from the set of incidences of G /(G)to the color-set C such that the adjacent incidences of G are assingned disdinct colors.If n: I(G)h->C is an incidence coloring of G and k =ICI, then we say that G is k -incidence colorable and n is called a k -incidence coloring. The minimum cardinality of C for which there exists an incidence coloring π: I(G) -C is called the incidence coloring number of G .In this paper we mainly discuss the incidence coloring number of the graph G. In the second chapter we determine the incidence coloring numbers of two classes of planar graphs (the flower graph and the prism): the incidence coloring number of the flower graph is equal to the sum of its maximum degree and 1; the incidence coloring number of the prism is equal to the sum of its maximum degree and 2. In the third chapter, we first discuss the relationship between a graph's incidence coloring number and its Mycielski graph's incidence coloringnumber: for any graph G of order n, whose incidence coloring number equals Δ(G) +1, if the twice of its maximum degree 2A(G) doesn't equal n, then the incidence coloring number of its Mycielski graph equals Δ(M(G)) + 1; if the twice of its maximum degree 2Δ(G) equals n, then the incidence coloring number of its Mycielski graph does not exceed Δ(M(G)) + 2. Secondly we study the incidence coloring numbers of the Mycielski graphs of...