20.500.12556/DKUM-51675 Game chromatic number of Cartesian product graphs Igralno kromatično število kartezičnih produktov grafov Obravnavamo igralno kromatično število ▫$chi_g$▫ kartezičnega produkta ▫$G Box H$▫ dveh grafov ▫$G$▫ in ▫$H$▫. Določimo točne vrednosti za ▫$chi_g(K_2 Box H$▫, ko je ▫$H$▫ pot, cikel ali poln graf. S pomočjo novo vpeljane "igre kombinacij" pokažemo, da igralno kromatično število ni omejeno znotraj razreda kartezičnih produktov dveh polnih dvodelnih grafov. Iz tega rezultata sledi, da igralno kromatično število ▫$chi_g(G Box H$▫ ni navzgor omejeno s kako funkcijo igralnih kromatičnih števil grafov ▫$G$▫ in ▫$H$▫. Analogen rezultat je izpeljan za igralno barvno število kartezičnih produktov grafov. The game chromatic number ▫$chi_g$▫ is considered for the Cartesian product ▫$G Box H$▫ of two graphs ▫$G$▫ and ▫$H$▫. Exact values of ▫$chi_g(K_2 Box H)$▫ are determined when $H$ is a path, a cycle, or a complete graph. By using a newly introduced "game of combination" we show that the game chromatic number is not bounded in the class of Cartesian products of two complete bipartite graphs. This result implies that the game chromatic number ▫$chi_g(G Box H)$▫ is not bounded from above by a function of game chromatic numbers of graphs ▫$G$▫ and ▫$H$▫. An analogous result is derived for the game coloring number of the Cartesian product of graphs. matematika teorija grafov kartezični produkt grafov igralno kromatično število mathematics graph theory Cartesian prodict game chromatic number true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 15:02:26 2015-07-10 15:02:26 2022-05-30 03:06:52 2021-05-09 03:36:55 2008 0 0 R72 (13 str.) no. 1 Vol. 15 2008 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 6973785 14761305 1077-8926 URN:SI:UM:DK:B0JP2ZAP http://www.combinatorics.org/Volume_15/PDF/v15i1r72.pdf 1 https://dk.um.si/Dokument.php?lang=slv&id=76235 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0