Injective Coloring Of Planar Graphs

All graphs are finite simple graphs in this paper.For a planar graph G,we use V(G),E(G),F(G),△(G),δ(G),g(G)and N(v)to denote the vertex set,edge set,face set,maximum degree,minimum degree,girth of G and the set of neighbors of v in G,respectively.For a vertex v ∈V(G),the vertex is called a k-vertex(or k+-vertex,or k--vertex)if d(v)=k(or d(v)≥k,or d(v)≤k).For a face f∈F(G),the face is called a k-face(or k+-face,or k--face)if d(f)=k(or d(f)≥k,or d(f)≤k).For(?)f∈F(G),we use b(f)to denote the boundary walk of f and write f=[x1x2…xk]if x1,x2,...,xk are the vertices of b(f)in the clockwise order.An injective k-coloring of a graph is a vertex coloring with k colors where two vertices have distinct colors if they have a common neighbor.If graph G has an injective k-coloring,the graph G is injective k-colorable.The injective chromatic number of G is the smallest integer k such that G has an injective k-coloring,denoted by χi(G).The coloring of graphs has always been an important area of graph theory research.With the development of the times,the types of coloring of graphs are becoming more and more.In addition to normal vertex coloring,there are 2-distance coloring,list coloring,vertex-distinguishing vertex coloring,BB-coloring and so on.Injective-coloring was first proposed by Hahn et al.in 2002.They proved that χi(G)≤Δ(Δ-1)+1 for any graph G with maximum degree Δ.This dissertation uses the properties of minimal counterexample and discharging,studies some conclusions about injective-coloring of plane graphs.In the first chapter,we introduced some basic concepts of graph and research status of injective-coloring.In the second chapter,we proved that χi(G)≤Δ(G)+2 for any plane graph G with g(G)≥5 and Δ(G)≥40.In the third chapter,we proved that χi(G)≤Δ+6 for any plane graph G with g(G)≥4,Δ(G)≥20 and without intersecting 4-cycles;we also proved that χi(G)≤Δ+4 for any plane graph G with Δ(G)≥16 and without intersecting 4~--cycles and 6~--cycles.