Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Browse
New in RUL
About RUL
In numbers
Help
Sign in
The independence coloring game on graphs
ID
Brešar, Boštjan
(
Author
),
ID
Mesarič Štesl, Daša
(
Author
)
PDF - Presentation file,
Download
(491,24 KB)
MD5: F020F1FCAC1A866D02833378C0CE1232
URL - Source URL, Visit
https://www.tandfonline.com/doi/abs/10.2989/16073606.2021.1947919
Image galllery
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.
Language:
English
Keywords:
graph
,
coloring
,
coloring game
,
competition-independence game
,
game chromatic number
,
tree
Work type:
Article
Typology:
1.01 - Original Scientific Article
Organization:
FRI - Faculty of Computer and Information Science
Publication status:
Published
Publication version:
Version of Record
Year:
2022
Number of pages:
Str. 1413-1434
Numbering:
Vol. 45, iss. 9
PID:
20.500.12556/RUL-143673
UDC:
519.174.7
ISSN on article:
1607-3606
DOI:
10.2989/16073606.2021.1947919
COBISS.SI-ID:
70914307
Publication date in RUL:
06.01.2023
Views:
342
Downloads:
51
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
Share:
Record is a part of a journal
Title:
Quaestiones mathematicae
Shortened title:
Quaest. math.
Publisher:
Taylor & Francis, National Inquiry Services Centre, South African Mathematical Society
ISSN:
1607-3606
COBISS.SI-ID:
514029849
Licences
License:
CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:
http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:
The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Secondary language
Language:
Slovenian
Keywords:
graf
,
barvanje
,
igra barvanja
,
neodvisna dominacijska igra
,
igralno kromatično število
,
drevo
Projects
Funder:
ARRS - Slovenian Research Agency
Project number:
P1-0297
Name:
Teorija grafov
Funder:
ARRS - Slovenian Research Agency
Project number:
J1-9109
Name:
Sodobne invariante grafov
Funder:
ARRS - Slovenian Research Agency
Project number:
J1-1693
Name:
Sodobni in novi metrični koncepti v teoriji grafov
Funder:
ARRS - Slovenian Research Agency
Project number:
N1-0095
Name:
Turanova števila in ekstremalni problemi za poti
Similar documents
Similar works from RUL:
Similar works from other Slovenian collections:
Back