Injective Coloring Of Planar Graphs On The Condition Of Girth At Least 5

Let G=(V, E) be a simple finite graph. The injective k-coloring of G is a map c:V(G)→{1,2,…,k}, where the two vertices in G with the same neighbor have different colors. That is to say for any vertices u, v with the same neighbor, satisfying c(u)≠c(v). If G has a injective k-coloring, then we say G is injective k-colorable, and the minimal integer k is called injective chromatic number of G, denoted by Xi{G). Assign each vertex v ∈ V(G) a colore set L(v), then L={L(v)|v ∈ v(G)} is said to be a color list of G, and different vertices can have different coloring sets. For a given color list L, c is called an injective L-coloring of G if c is an injective coloring such that c(v) ∈ L(v), for any v∈V(G), and G is injective L-colorable. If for any color list L, such that |L(v)|≥k,G is injective L-colorable, then G is said to be injective k-optional. The injective chromatic number of G is denoted by xil(G)=min{k|G is injective k-optional}.This master thesis has two chapters, focusing on injective coloring of planar graphs on the condition of with girth at least 5. We improve several previous results. The first chapter gives a survey of the injective coloring problem and introduces some definitions and symbols. The second chapter mainly discusses the injective coloring of planar graphs on the condition of with girth at least 5.