On the game chromatic number of Cartesian product of graphs

• Main Authors: Encinas, Sarah Jane K., Yuson, Berlyn Grace C.
• Format: text
• Language: English
• Published: Animo Repository 2010
• Subjects: Graph theory; Graph coloring; Mathematics
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/5343
• Institution: De La Salle University

The game chromatic number refers to the smallest integer k such that the first player Alice is assumed of a victory in the coloring game variety wherein Alice and Bob take turns in coloring vertices of a graph, with the only rule that adjacent vertices cannot have the same color. Alice wins if all vertices have been colored. Otherwise, Bob wins. This thesis provides the proofs for the game chromatic number of special classes of graphs which includes paths, cycles, complete graphs, complete bipartite graphs and complete bipartite-1-factor graphs, communicated by Professor Kiyoshi Ando of the University of Electrocommunications, Tokyo, Japan. The game chromatic number of the Cartesian product of graphs, specifically the product of a complete graph of order 2 with a path, a cycle and a complete graph were also discussed based on the paper Game chromatic number of Cartesian product graphs written by T. Bartnicki, B. Bresar, J. Grytczuk, M. Kovse, Z. Miechowics and I. Peterin, published on May 12, 2008 on The Electronic Journal of Combinatorics.