Search the digital library catalog

Abstract: 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.
Keywords: graph, coloring, coloring game, competition-independence game, game chromatic number, tree
Published in DKUM: 09.08.2024; Views: 99; Downloads: 5
Full text (852,33 KB)
This document has many files! More...

Abstract: The square ▫$G^2$▫ of a graph ▫$G$▫ is obtained from ▫$G$▫ by adding edges joining all pairs of nodes at distance 2 in ▫$G$▫. In this note we prove that ▫$chi((C_mBox C_n)^2) le 6$ for $m, n ge 40$▫. This confirms Conjecture 19 stated in [É. Sopena, J. Wu, Coloring the square of the Cartesian product of two cycles, Discrete Math. 310 (2010) 2327-2333].
Keywords: matematika, teorija grafov, kromatično število, kartezični produkt, označevanje grafov, kvadrat grafa, mathematics, graph theory, chromatic number, Cartesian product, graph labeling, square if a graph
Published in DKUM: 10.07.2015; Views: 1460; Downloads: 83
Link to full text

Abstract: Označitev grafa ▫$G$▫ je razlikovalna, če jo ohranja le trivialni avtomorfizem grafa ▫$G$▫. Razlikovalno kromatično število grafa ▫$G$▫ je najmanjše naravno število, za katero obstaja razlikovalna označitev grafa, ki je hkrati tudi dobro barvanje. Za vse ▫$k$▫ in ▫$n$▫ je določeno razlikovalno kromatično število kartezičnih produktov ▫$K_kBox K_n$▫. V večini primerov je enako kromatičnemu številu, kar med drugim odgovori na vprašanje Choia, Hartkeja and Kaula, ali obstajajo še kakšni drugi grafi, za katere velja enakost.
Keywords: teorija grafov, razlikovalno kromatično število, grafovski avtomorfizem, kartezični produkt grafov, graph theory, distinguishing chromatic number, graph automorphism, Cartesian product of graphs
Published in DKUM: 10.07.2015; Views: 1152; Downloads: 96
Link to full text

Abstract: Obravnavana so vozliščna, povezavna in skupna barvanja grafov Sierpińskijevih rešetk ▫$S_n$▫, Sierpińskijevih grafov ▫$S(n,k)$▫, grafov ▫$S^+(n,k)$▫ in grafov ▫$S^{++}(n,k)$▫. V posebnem je dokazano, da velja ▫$chi''(S_n)$▫, ▫$chi'(S(n,k))$▫, ▫$chi(S^+(n,k))$▫, ▫$chi(S^{++}(n,k))$▫, ▫$chi'(S^+(n,k))$▫ in ▫$chi'(S^{++}(n,k))$▫.
Keywords: matematika, teorija grafov, Sierpińskijeve rešetke, Sierpińskijevi grafi, kromatično število, kromatični indeks, skupno kromatično število, mathematics, graph theory, Sierpiński gasket graphs, Sierpiński graphs, chromatic number, chromatic index, total chromatic number
Published in DKUM: 10.07.2015; Views: 1075; Downloads: 95
Link to full text

Abstract: 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.
Keywords: matematika, teorija grafov, kartezični produkt grafov, igralno kromatično število, mathematics, graph theory, Cartesian prodict, game chromatic number
Published in DKUM: 10.07.2015; Views: 1142; Downloads: 257
Link to full text