The Incidence Coloring And Adjacent Vertex Distinguishing Incidence Coloring Of Graphs

Let graph G=(V, E), I(G)={(v, e)|v∈V, e∈E, v is incident with e} is called the set of incidences of G. We say that two incidences (v, e) and (w, f)are neighborly provided one of the following holds: (1) v=w ; (2) e=f ; (3) vw=e or vw=f.An incidence coloring of G is a mappingσfrom I(G) to a color set C such that any two neighborly incidences have different images. Ifσ: I(G)→C is an incidence coloring of G and |C|=k, k is a positive integer, then we say that G is k- incidence colorable andσis a k - incidence coloring of G; The minimum value of k such that G is k -incidence colorable is called the incidence chromatic number of G, and is denoted byχ_i(G), namelyχ_i(G) = min {|C||σ: I(G)→C is an incidence coloring of G}.In this dissertation, we shall study the incidence coloring ofθ- graph, then we shall define the concepts of the adjacent vertex distinguishing incidence coloring and the adjacent vertex distinguishing incidence chromatic number of graphs and determine the adjacent vertex distinguishing incidence chromatic number of some graphs. There are five chapters in this dissertation. The arrangement is as follows:In the second chapter, we shall determine the incidence chromatic number ofθ- graph.In the third chapter, we shall define the concepts of the adjacent vertex distinguishing incidence coloring and the adjacent vertex distinguishing incidence chromatic number of graphs: For graph G, let Q_u={(u, uu')|u'∈N(u)}U{(u', u'u)|u'∈N(u)},σ: I(G)→C is a k- incidence coloring of graph G, C_u denotes the set of colors assigned to Q_u. If for any uv∈E(G), C_u≠C_v, then we callσis a k-adjacent vertex distinguishing incidence coloring of G andχ_ai(G)=min{k| there exists a k- adjacent vertex distinguishing incidence coloring of G} is the adjacent vertex distinguishing incidence chromatic number of G. We shall determine the adjacent vertex distinguishing incidence chromatic number of paths, cycles, stars, fans, wheels, complete graphs. In the fourth chapter, we shall determine the adjacent vertex distinguishing incidence chromatic number of complete bipartite graphs, C_m,·F_n graphs and one type ofθ- graph.In the fifth chapter, we shall determine the adjacent vertex distinguishing incidence chromatic number of two types of join-graph.