| Popis: |
V magistrskem delu bomo predstavili igro barvanja vozlišč grafa in igralno kromatično število grafa. Podrobneje si bomo pogledali igro barvanja vozlišč grafa na kartezičnih, direktnih in leksikografskih produktih nekaterih družin grafov. Pri kartezičnih produktih K_2 square P_n, n in NN, K_2 square C_n, n geq 3, K_2 square K_n, n in NN, in toroidnih grafih, ki jih dobimo s kartezičnim produktom dveh ciklov, C_{2m} square C_n, mgeq 3, n geq 7, bomo predstavili in pokazali natančne vrednosti igralnih kromatičnih števil le-teh. Predstavili bomo tudi igralna kromatična števila naslednjih direktnih produktov: K_{1,n} times K_{1,m}, m,n in NN, K_{m,n} times K_{a,b}, a,b,n geq 2, m in NN, P_n times K_{1,m}, m geq 3, n geq 2, in P_2 times W_n, n geq 3, P_2 times C_n, n geq 3. Nazadnje bomo predstavili še igralna kromatična števila naslednjih leksikografskih produktov: P_2 circ P_n, n geq 2, P_2 circ K_{1,n}, n in NN, in P_2 circ W_n, n geq 8. In this master’s thesis we will present the vertex coloring game and the game chromatic number of graphs. We will take a closer look at the vertex coloring game on the Cartesian, direct, and lexicographic products of certain graph families. We will determine the exact values of the game chromatic number of the Cartesian products K_2 square P_n, n in NN, K_2 square C_n, n geq 3, K_2 square K_n, n in NN, and toroidal grid graphs C_{2m} square C_n, mgeq 3, n geq 7, which we obtain with the Cartesian product of two cycles. We will also derive the game chromatic number of the following direct products: K_{1,n} times K_{1,m}, m,n in NN, K_{m,n} times K_{a,b}, a,b,n geq 2, m in NN, P_n times K_{1,m}, m geq 3, n geq 2, and P_2 times W_n, n geq 3, P_2 times C_n, n geq 3. Finally, we will present the game chromatic number of the following lexicographic products: P_2 circ P_n, n geq 2, P_2 circ K_{1,n}, n in NN, and P_2 circ W_n, n geq 8. |
