Game chromatic number of Cartesian product graphs

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

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;

Data

Language:	English
Year of publishing:	2008
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	519.17
COBISS:	14761305
ISSN:	1077-8926
Views:	703
Downloads:	214
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	Igralno kromatično število kartezičnih produktov grafov
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;kartezični produkt grafov;igralno kromatično število;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	R72 (13 str.)
Volume:	ǂVol. ǂ15
Issue:	ǂno. ǂ1
Chronology:	2008
ID:	1473580