| Naslov: | The independence coloring game on graphs |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Mesarič Štesl, Daša (Avtor) |
|---|
| Datoteke: |  Bresar-2022-The_independence_coloring_game_on.pdf (852,33 KB)
MD5: D63234FB6C8E69A1CB0C44A958211CB3
 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  |
|---|
| UDK: | 519.174.7 |
|---|
| COBISS.SI-ID: | 70914307 |
|---|
| DOI: | 10.2989/16073606.2021.1947919 |
|---|
| ISSN pri članku: | 1607-3606 |
|---|
| Datum objave v DKUM: | 09.08.2024 |
|---|
| Število ogledov: | 99 |
|---|
| Število prenosov: | 3 |
|---|
| Metapodatki: |     |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
