Majority coloring game

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

Abstract

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 Jagiellonski w Krakowie]
Gabriel Jakóbczak,,
-
-
Journal seriesDiscrete Applied Mathematics, ISSN 0166-218X, (N/A 70 pkt)
Issue year2019
Vol255
Pages15-20
Publication size in sheets0.5
Keywords in EnglishGame chromatic number; Majority coloring; Majority game chromatic number
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
DOIDOI:10.1016/j.dam.2018.07.020
URL https://www.sciencedirect.com/science/article/pii/S0166218X18304086?via%3Dihub
Languageen angielski
Score (nominal)70
Score sourcejournalList
ScoreMinisterial score = 70.0, 20-10-2019, ArticleFromJournal
Publication indicators Scopus Citations = 0; WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.17; WoS Impact Factor: 2017 = 0.932 (2) - 2017=1.008 (5)
Citation count*
Cite
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.
Back
Confirmation
Are you sure?