Game chromatic number of Cartesian product graphs

T. Bartnicki (Avtor), Boštjan Brešar (Avtor), J. Grytczuk (Avtor), Matjaž Kovše (Avtor), Z. Miechowicz (Avtor), Iztok Peterin (Avtor)

Povzetek

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.

Ključne besede

matematika;teorija grafov;kartezični produkt grafov;igralno kromatično število;mathematics;graph theory;Cartesian prodict;game chromatic number;

Podatki

Jezik:	Angleški jezik
Leto izida:	2008
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK:	519.17
COBISS:	14761305
ISSN:	1077-8926
Št. ogledov:	703
Št. prenosov:	214
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Igralno kromatično število kartezičnih produktov grafov
Sekundarni povzetek:	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.
Sekundarne ključne besede:	matematika;teorija grafov;kartezični produkt grafov;igralno kromatično število;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	R72 (13 str.)
Letnik:	ǂVol. ǂ15
Zvezek:	ǂno. ǂ1
Čas izdaje:	2008
ID:	1473580