The Study Of Two Types Of Combinatorial Game

This thesis is divided into two parts.In the first part(the first four chapters),we study some Nim-type games.In the second part(the fifth and the sixth chapters),we study painting game on graphs.Nim game perhaps is the most classic Combinatorial game.Relating combinato-rial game papers had studied a lot of the variant version of Nim game.For example,Moore introduced and solved Nimk game in 1910,Schwartz introduced Bounded Nim game in 1971,Ablert and Nowakowski introduced Greedy Nim game in 2004,Chan and Low introduced Nim with a pass(also called Nim*)in 2015.In Chapter 1,we introduce the rules and winning strategies for this Nim-type games.In Chapter 2 and Chapter 3,we propose two Nim-type games:Bounded greedy Nim game and Greedy Nimk game.Bounded greedy Nim game is the combination of Bounded Nim game and Greedy Nimk game,while Greedy Nimk game is the combination of Greedy Nim game and Nimk game.As we all known,any slight modify of the rule may result in radical changes in the winning strategy of the game.The winning strategies of Bounded greedy Nim game and Greedy Nimk have a large differences with none of the original strategy of the Nim game,i.e.the original strategies is no longer apply to the New Nim-type games.In Chapter 2 and Chapter 3,we also give the complete winning strategies for Bounded greedy Nim game and Greedy Nimk In the Chapter 4,we discuss Nim with a pass,some partial results on this game were obtained by Chan and Low in[12].We generalize a few lemmas in[12]and present solutions for more cases of this game.To find the complete solution for this game is still an open problem.In Chapter 5 and 6,we study list coloring and online list coloring of graph.Assume G is a graph and f:V(G)?N is a mapping.Given an integer m,let f(m)be the extension of f to the graph G(?)Km for which f(m)(v)=|v(G)| for each vertex v of Km Let mc(G,f)and mp(G,f)denote the minimum number such that G(?)Km is not f(m)-choosable and is not f(m)-paintable.We determine mc(G,f)and mp(G,f)for all mapings f.Our theorem generalize the results about list coloring and online list coloring in[5].Interestingly,the results of mc(G,f)and mp(G,f)are related to generalized Dyck paths.