| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava
Prva stran > Izpis gradiva

Izpis gradiva Pomoč

Naslov:The independence coloring game on graphs
Avtorji:ID Brešar, Boštjan (Avtor)
ID Mesarič Štesl, Daša (Avtor)
Datoteke:.pdf Bresar-2022-The_independence_coloring_game_on.pdf (852,33 KB)
MD5: D63234FB6C8E69A1CB0C44A958211CB3
 
URL https://doi.org/10.2989/16073606.2021.1947919
 
Jezik:Angleški jezik
Vrsta gradiva:Znanstveno delo
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
Opis: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.
Ključne besede:graph, coloring, coloring game, competition-independence game, game chromatic number, tree
Status publikacije:Objavljeno
Verzija publikacije:Objavljena publikacija
Poslano v recenzijo:21.01.2021
Datum objave:19.07.2021
Založnik:NISC
Leto izida:2022
Št. strani:Str. 1413-1434
Številčenje:Letn. 45, Št. 9
PID:20.500.12556/DKUM-89747 Novo okno
UDK:519.174.7
COBISS.SI-ID:70914307 Novo okno
DOI:10.2989/16073606.2021.1947919 Novo okno
ISSN pri članku:1607-3606
Datum objave v DKUM:09.08.2024
Število ogledov:99
Število prenosov:10
Metapodatki:XML DC-XML DC-RDF
Področja:Ostalo
:
BREŠAR, Boštjan in MESARIČ ŠTESL, Daša, 2022, The independence coloring game on graphs. Quaestiones mathematicae [na spletu]. 2022. Vol. 45, no. Št. 9, p. 1413–1434. [Dostopano 7 april 2025]. DOI 10.2989/16073606.2021.1947919. Pridobljeno s: https://dk.um.si/IzpisGradiva.php?lang=slv&id=89747
Kopiraj citat
  
Skupna ocena:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:Bookmark and Share



Podobna dela iz ostalih repozitorijev:

Ni podobnih del

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Quaestiones mathematicae
Skrajšan naslov:Quaest. math.
Založnik:NISC
ISSN:1607-3606
COBISS.SI-ID:514029849 Novo okno

Gradivo je financirano iz projekta

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

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.
Začetek licenciranja:19.07.2021

Sekundarni jezik

Jezik:Slovenski jezik
Ključne besede:graf, barvanje, igra barvanja, neodvisna dominacijska igra, igralno kromatično število, drevo


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici