2-Coloring number revisited - Publication - MOST Wiedzy

Search

2-Coloring number revisited

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

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 22 times

Recommended for you

Meta Tags