Search
Abstract
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.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (3)
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2019.09.009
- License
- Copyright (2019 Elsevier B.V.)
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
THEORETICAL COMPUTER SCIENCE
no. 796,
pages 187 - 195,
ISSN: 0304-3975 - Language:
- English
- Publication year:
- 2019
- Bibliographic description:
- Janczewski R., Obszarski P., Turowski K.: 2-Coloring number revisited// THEORETICAL COMPUTER SCIENCE -Vol. 796, (2019), s.187-195
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2019.09.009
- Verified by:
- Gdańsk University of Technology
seen 154 times