Let G=(V,E) be a graph with the vertex set V(G), the edge set E(G) andmaximum degree ?(G). Suppose that v is an arbitrary vertex in V(G) and e isan edge in E(G) incident to v . The pair (v,e) is called an incidence in G. The setof all of incidences in G is denoted by I(G). Two incidences (v,e) and (w,f) are adjacent if one of the following threeconditions holds: • v=w; • e=f; • The edge vw equals e or f. The incidence coloring of G is a mapping ?:I(G)?S (S is the color set) in which adjacent incidences receive different colors. If |S|=k, then G is said k -incidence colorable. The minimum k for which G is k -incidence colorable, isthe incidence coloring number of G denoted by ? i (G). The concept of incidence coloring was introduced by Brualdi and Massey. They proved: ?(G)+1? ?i(G)? 2?(G) They conjectured that for ? 2 the upper bound can never be attained and ingeneral: ?i(G)? ?(G)+2 This conjecture is known as ICC. Although ICC is disproved in general case, it is proved for several In this thesis we have a comprehensive survey on the concept of incidence coloring of graphs and incidence coloring conjectures.
