Game chromatic number of Cartesian product graphs

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

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Game chromatic number of Cartesian product graphs
Authors:	ID Bartnicki, T. (Author) ID Brešar, Boštjan (Author) ID Grytczuk, J. (Author) ID Kovše, Matjaž (Author) ID Miechowicz, Z. (Author) ID Peterin, Iztok (Author)
Files:	http://www.combinatorics.org/Volume_15/PDF/v15i1r72.pdf
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FERI - Faculty of Electrical Engineering and Computer Science
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
Year of publishing:	2008
Number of pages:	R72 (13 str.)
Numbering:	Vol. 15, no. 1
PID:	20.500.12556/DKUM-51675
UDC:	519.17
ISSN on article:	1077-8926
COBISS.SI-ID:	14761305
NUK URN:	URN:SI:UM:DK:B0JP2ZAP
Publication date in DKUM:	10.07.2015
Views:	1142
Downloads:	265
Metadata:
Categories:	Misc.
:	BARTNICKI, T., BREŠAR, Boštjan, GRYTCZUK, J., KOVŠE, Matjaž, MIECHOWICZ, Z. and PETERIN, Iztok, 2008, Game chromatic number of Cartesian product graphs. The Electronic journal of combinatorics [online]. 2008. Vol. 15, no. 1. [Accessed 31 March 2025]. Retrieved from: http://www.combinatorics.org/Volume_15/PDF/v15i1r72.pdf Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Unravelling the role of nitrogen in surface chemistry and oxidation evolution of deep cryogenic treated high-alloyed ferrous alloy
The evolution of microstructure and mechanical properties of Zn-0.8Mg-0.2Sr alloy prepared by casting and extrusion

Similar works from other repositories:

Rak dojk v Sloveniji

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	The Electronic journal of combinatorics
Shortened title:	Electron. j. comb.
Publisher:	N.J. Calkin and H.S. Wilf
ISSN:	1077-8926
COBISS.SI-ID:	6973785

Secondary language

Language:	Unknown
Title:	Igralno kromatično število kartezičnih produktov grafov
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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back