Majority coloring game

Bartłomiej Bosek , Jarosław Grytczuk , Gabriel Jakóbczak


A 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.
Author Bartłomiej Bosek - [Uniwersytet Jagiellonski w Krakowie]
Bartłomiej Bosek,,
, Jarosław Grytczuk (FMIS / DAC)
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Gabriel Jakóbczak - [Uniwersytet Jagielloński w Krakowie (UJ)]
Gabriel Jakóbczak,,
- Uniwersytet Jagielloński w Krakowie
Journal seriesDiscrete Applied Mathematics, ISSN 0166-218X
Issue year2019
Publication size in sheets0.5
Keywords in Polishrozgrywana liczba chromatyczna, kolorowanie większościowe
Keywords in EnglishGame chromatic number; Majority coloring; Majority game chromatic number
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
Abstract in PolishPraca dotyczy gry w kolorowanie większościowe grafów.
Languageen angielski
Score (nominal)70
Score sourcejournalList
ScoreMinisterial score = 70.0, 05-02-2020, ArticleFromJournal
Publication indicators Scopus Citations = 0; WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.263; WoS Impact Factor: 2018 = 0.983 (2) - 2018=1.029 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?