Majority coloring game
Bartłomiej Bosek , Jarosław Grytczuk , Gabriel Jakóbczak
AbstractA majority coloring of a graph is a coloring of its vertices such that for each vertex , at least half of the neighbors of have different color than . Let denote the least number of colors needed for a majority coloring of a graph . It is well known and easy to prove that for every graph . We consider a game-theoretic variant of this parameter, the majority game chromatic number , defined via a two person coloring game in which one of the players tries to produce a majority coloring of the whole graph, while the other tends to prevent it. We prove that is in general unbounded. On the other hand, it is not hard to see that is not greater than , the game coloring number of . We improve this trivial bound for some classes of graphs. In particular, we prove that for every complete binary tree . This may suggest that is bounded for graphs with bounded coloring number . However, we prove that, contrary to this intuition, is unbounded for graphs with.
|Journal series||Discrete Applied Mathematics, ISSN 0166-218X|
|Publication size in sheets||0.5|
|Keywords in Polish||rozgrywana liczba chromatyczna, kolorowanie większościowe|
|Keywords in English||Game chromatic number; Majority coloring; Majority game chromatic number|
|Abstract in Polish||Praca dotyczy gry w kolorowanie większościowe grafów.|
|Score||= 70.0, 05-02-2020, ArticleFromJournal|
|Publication indicators||= 0; = 0; : 2018 = 1.263; : 2018 = 0.983 (2) - 2018=1.029 (5)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.