20.500.12556/DKUM-89747 The independence coloring game on graphs We propose a new coloring game on a graph, called the independence coloring game, which is played by two players with opposite goals. The result of the game is a proper coloring of vertices of a graph G, and Alice’s goal is that as few colors as possible are used during the game, while Bob wants to maximize the number of colors. The game consists of rounds, and in round i, where i = 1, 2,, … , the players are taking turns in selecting a previously unselected vertex of G and giving it color i (hence, in each round the selected vertices form an independent set). The game ends when all vertices of G are selected (and thus colored), and the total number of rounds during the game when both players are playing optimally with respect to their goals, is called the independence game chromatic number, χig(G), of G. In fact, four different versions of the independence game chromatic number are considered, which depend on who starts a game and who starts next rounds. We prove that the new invariants lie between the chromatic number of a graph and the maximum degree plus 1, and characterize the graphs in which each of the four versions of the game invariant equals 2. We compare the versions of the independence game chromatic number among themselves and with the classical game chromatic number. In addition, we prove that the independence game chromatic number of a tree can be arbitrarily large. graph coloring coloring game competition-independence game game chromatic number tree graf barvanje igra barvanja neodvisna dominacijska igra igralno kromatično število drevo true false true NISC Angleški jezik Slovenski jezik Znanstveno delo 2024-08-09 08:25:32 2024-08-09 08:44:09 2024-08-10 03:47:44 0000-00-00 00:00:00 2022 0 0 Str. 1413-1434 Št. 9 Letn. 45 2022 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2021-01-21 0000-00-00 2021-07-19 519.174.7 70914307 10.2989/16073606.2021.1947919 1607-3606 Bresar-2022-The_independence_coloring_game_on.pdf Bresar-2022-The_independence_coloring_game_on.pdf 1 D63234FB6C8E69A1CB0C44A958211CB3 405a989fda87dc3f8bd11d0f15c2dee8d1d5959a8ec8f2d7f0b3c9b6e3e02737 6dca5a33-561a-11ef-97b6-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=182166 https://doi.org/10.2989/16073606.2021.1947919 0 2ff23f8d-5618-11ef-97b6-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=182165 Fakulteta za naravoslovje in matematiko 0 0 0