Injective Edge Coloring Of Graphs

All graphs considered in this paper are finite,simple and undirected.Let G be a graph,we use V(G),E(G),F(G),?(G)and g(G)to denote its vertex set,edge set,face set,the maximum degree and the girthA k-injective coloring of G is a coloring of the vertices of G,f:Y(G)?C={1,2,…,k},such that if any two vertices v1,v2 adjacent to the same neighbor,then f(v1)?f(v2).We denote ?i(G)=min{k|G has a k-injective coloring}.A k-injective edge coloring of G is a coloring of the edges of G,f:E(G)?C={1,2,…,k},such that if e1,e2,e3 are three consecutive edges in G,then f(e1)?f(es).We denote?'i(G)=min{k|G has a k-injective edge coloring}.In this paper,we mainly apply discharge and minimal counterexample to study the structural properties of related graph classes.We mainly study the ?'i(G)of planar graphs under the limits of the maximum degree and the girth and without some short cycles,and the ?'i(G)of some special graph classes.This thesis includes four sections.In the first section,we show some related definitions and research status of injective coloring and injective edge coloring.In the second section,we prove the upper bound of ?'i(G)is 3?(G)-3 for planar graphs with girth at least 6 and in which 6-cycle and 7--cycle don't intersect.In the third section,we discuss the upper bound of ?'i(G)is 3?(G)-2 for planar graph with no k-cycle(5?k?10)and the 4--cycle are non-intersect each other.In the fourth section,we discuss the ?'i(G)of some special graph classes.