Injective Coloring Of Plane Graphs

All graphs considered in this paper are finite simple graphs. An injective k-coloring of a graph G is a mapping （?）:V（G）→{1,2,…k} such that （?）（u）≠（?）（v） whenever u, v have a common neighbor in G. The injective chromatic number of G, denoted by Xi（G）, is the least integer k such that G has an injective k-coloring. We use χli（G） to denote the injective list chromatic number of G.In2002, Hahn et al. first introduced the injective coloring which is originated from complexity theory. They studied the injective chromatic number of hypercube, and showed application of it in the theory of error-correcting codes. Injective coloring is a close relative to L（0,1）-labeling and the coloring of square of graphs. In2010, Luiar posed a conjecture that if G is a plane graph then Xi （G）≤5ifâ–³=3, χi（G）≤△+5if4≤△≤7, and χi（G）≤（?）（3△）/2（?）₁if△≥8.The upper of the conjecture is tight.This master thesis, consisting of four chapters, focuses on injective coloring on the condition of without short cycles for plane graphs. We make some improvement on several previous results. In the first chapter, we introduce some definitions and give a brief survey of injective coloring. In the second chapter, we mainly discuss the list injective coloring of plane graphs with girth at least5. In the third chapter, we study some sufficient conditions for χli（G）≤△A+1and χli（G）=â–³. In the fourth chapter, we give a smaller upper bound for list injective chromatic number of plane graphs containing no3-,4-,8-cycles.