Vaš brskalnik ne omogoča JavaScript!
JavaScript je nujen za pravilno delovanje teh spletnih strani. Omogočite JavaScript ali pa uporabite sodobnejši brskalnik.
Nacionalni portal odprte znanosti
Odprta znanost
DiKUL
slv
|
eng
Iskanje
Brskanje
Novo v RUL
Kaj je RUL
V številkah
Pomoč
Prijava
The independence coloring game on graphs
ID
Brešar, Boštjan
(
Avtor
),
ID
Mesarič Štesl, Daša
(
Avtor
)
PDF - Predstavitvena datoteka,
prenos
(491,24 KB)
MD5: F020F1FCAC1A866D02833378C0CE1232
URL - Izvorni URL, za dostop obiščite
https://www.tandfonline.com/doi/abs/10.2989/16073606.2021.1947919
Galerija slik
Izvleček
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.
Jezik:
Angleški jezik
Ključne besede:
graph
,
coloring
,
coloring game
,
competition-independence game
,
game chromatic number
,
tree
Vrsta gradiva:
Članek v reviji
Tipologija:
1.01 - Izvirni znanstveni članek
Organizacija:
FRI - Fakulteta za računalništvo in informatiko
Status publikacije:
Objavljeno
Različica publikacije:
Objavljena publikacija
Leto izida:
2022
Št. strani:
Str. 1413-1434
Številčenje:
Vol. 45, iss. 9
PID:
20.500.12556/RUL-143673
UDK:
519.174.7
ISSN pri članku:
1607-3606
DOI:
10.2989/16073606.2021.1947919
COBISS.SI-ID:
70914307
Datum objave v RUL:
06.01.2023
Število ogledov:
361
Število prenosov:
51
Metapodatki:
Citiraj gradivo
Navadno besedilo
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Kopiraj citat
Objavi na:
Gradivo je del revije
Naslov:
Quaestiones mathematicae
Skrajšan naslov:
Quaest. math.
Založnik:
Taylor & Francis, National Inquiry Services Centre, South African Mathematical Society
ISSN:
1607-3606
COBISS.SI-ID:
514029849
Licence
Licenca:
CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
Povezava:
http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:
Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.
Sekundarni jezik
Jezik:
Slovenski jezik
Ključne besede:
graf
,
barvanje
,
igra barvanja
,
neodvisna dominacijska igra
,
igralno kromatično število
,
drevo
Projekti
Financer:
ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:
P1-0297
Naslov:
Teorija grafov
Financer:
ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:
J1-9109
Naslov:
Sodobne invariante grafov
Financer:
ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:
J1-1693
Naslov:
Sodobni in novi metrični koncepti v teoriji grafov
Financer:
ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:
N1-0095
Naslov:
Turanova števila in ekstremalni problemi za poti
Podobna dela
Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:
Nazaj