Indicated coloring of graphs |
| |
Authors: | Andrzej Grzesik |
| |
Institution: | Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, ul. Prof. St. Lojasiewicza 6, PL-30-348 Krakow, Poland |
| |
Abstract: | We study a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent realization of this project. The smallest number of colors necessary for Ann to win the game on a graph (regardless of Ben’s strategy) is called the indicated chromatic number of , and denoted by . We approach the question how much differs from the usual chromatic number . In particular, whether there is a function such that for every graph . We prove that cannot be linear with leading coefficient less than . On the other hand, we show that the indicated chromatic number of random graphs is bounded roughly by . We also exhibit several classes of graphs for which and show that this equality for any class of perfect graphs implies Clique-Pair Conjecture for this class of graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|