Research On Indicated Chromatic Number Of Graph

Let G=(V,E)be a graph where V is the set of vertices of G and E is the set of edges of G.Indicated coloring is a simple graph coloring game in which there are two players collectively coloring the vertices of a graph in the following way.In each round,the first player(Ann)selects a uncolored vertex,and then the second player(Ben)colors it normally,that is adjacent vertices are different colors,and they use a fixed set of colors.The two players have opposite goals.The goal of Ann is to achieve a proper coloring of the whole graph G,while Ben is trying to prevent the realization of this project.Regardless of Ben’s strategy,the smallest number of colors necessary for Ann to win the game on a graph G is called the indicated chromatic number of G,and is denoted by χi(G).In this thesis,we first give a conclusion for a graph G whose clique number is equal to the indicator chromatic number,that is χi(Gn□Ka)=χi(G),and we extend this conclusion to any tree T:χi(G□T)=χi(G),G□T means the graph G taking the Cartesian product with tree T,it is still a graph whose set of vertices is V(G)× V(T),and specifies that points(u,v)and(u’,v’)are adjacent if and only if u=u’ and vv’∈(T),or v=v’ and uu’∈E(G).Next,we study the indication coloring number of the Direct product graph G1 × G2 of two graphs G1 and G2,the vertex sets of the Direct product G1 × G2 are V(G1 × G2)={(x,y)|x ∈V(G1),y∈(G2)},the edge sets are E(G1 × G2)={(x,y)～(x’,y’)|xx’∈E(G1),yy’∈E(G2)}.Then,we also give the indicator chromatic number of the Split graph and M?bius ladder graph.And then,we also study the diamond correlation graph and a kind of Cubic graph,and get their indicator chromatic number.Finally,we also study the indicator chromatic number of Interlacing graph,found its lower bound,and find a connected,non-complete 4-regular graph whose indicator chromatic number is equal to 5.