Game Chromatic Number of Tadpole Graph, Broom Graph, and Tribune Graph

Abstract

Graph coloring game is one of application in graph theory. The goal in this article is determine game chromatic number of tadpole graph, broom graph, and tribune graph. The graphs are simple, connected, and undirected and thus eligible for playing graph coloring game. Given two players with the first player is called A and second player is called B coloring vertex of graph G with a set of colors C={c_1,c_2,c_3, ..., c_k}. A must to make sure that all vertex of G has colored and B must try to prevent A coloring of all vertex. The first step was taken by A as first player, two players take turns coloring vertex of graph G, with rule that every vertex have different color from the neighbourhood. If all vertex of graph G have been colored, then A win or B win if some vertex hasn’t colored. The smallest number of k if A has a strategy to win at graph G with k color, then k called game chromatic number which is denoted by χ_g (G). The strategy to win this game is coloring the biggest degree of vertex in graph first. The result obtained from this paper is A win the game with the strategy of first coloring the largest degrees of vertex. So, exact of game chromatic number of tadpole graph is 3, broom graph is 2 or 3 with several conditions, and tribune graph is 3 or 4 with several conditions.

Keywords

• graph coloring games
• chromatic numbers
• tadpole graph
• broom graph
• tribune graph.