Two Graph Coloring Problems With Some Restricted Conditions

Given a graph G=(V,E),a proper coloring of G is an assignment of colors to vertices(edges)of G such that any two adjacent vertices(edges)receive distinct colors.The chromatic number(chromatic index)of G,denoted by x(G')(x'(G)),is the smallest positive integer m such that G is proper m-colorable.An injective k-coloring of a graph G is a mapping C:V(G)?{1,2,...,k} such that C(u)?C(v)whenever u and v have a common neighbor in G.The injective chromatic number of G,denoted by xi(G),is the smallest integer k such that G has an injective k-coloring.A list assignment of a graph G is a mapping L that assigns a list of L(v)colors to each vertex v?V(G).Given a list assignment L of G,an injective coloring C of G is called an injective L-coloring if C(v)?L(v)for every v?V(G).A graph G is injectively k-choosable if G has an injective L-coloring for any list assignment L with |L(v)|>k for each v?V(G).The injective choosability number of G,denoted by Xil(G),is the smallest integer k such that G is injective k-choosable.We prove that xil(G)?max{?+4,14} if G is a planar graph with g(G)?5 and maximum degree ?.A strong edge coloring of a graph is a proper edge coloring in which edges of every path with length at most 3 are colored with different colors.The strong chromatic index,denoted by X's(G),is the smallest nonnegative integer k such that G has a k-strong edge coloring.If graph G contains neither P5 nor C5 as induced subgraphs,G is(P5,C5)-free.In this paper,we prove that if graph G is(P5,C5)-free and has maximum degree ?,then#12We mainly study injective coloring problem on planar graphs and strong edge coloring problem.The thesis consists of four chapters.In Chapter 1,we introduce the background and main progress on injective coloring and strong edge coloring problems of graphs,some basic definitions and symbols to be used in this paper and list the main results of this thesis.In Chapter 2,we prove that Xil(G)<max{?+4,14} if G is a planar graph with g(G)?5 and maximum degree ?.In Chapter 3,we prove that if graph G is(P5,C5)-free and has maximum degree?,then#12In Chapter 4,we give some further research problems.