Wyszukiwarka
Abstrakt
2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow quadratically as a function of the maximum degree of a graph, whereas the game chromatic number is always at most linear. Moreover, we establish the values of the 2-coloring number for several graph classes, such as complete k-partite graphs, cacti and thorny graphs, trees and subcubic graphs. It is shown that in all these cases one may compute the exact value in a polynomial time.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2019.09.009
- Licencja
- Copyright (2019 Elsevier B.V.)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
THEORETICAL COMPUTER SCIENCE
nr 796,
strony 187 - 195,
ISSN: 0304-3975 - Język:
- angielski
- Rok wydania:
- 2019
- Opis bibliograficzny:
- Janczewski R., Obszarski P., Turowski K.: 2-Coloring number revisited// THEORETICAL COMPUTER SCIENCE -Vol. 796, (2019), s.187-195
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2019.09.009
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 206 razy