Relaxed very asymmetric coloring games
type: Item
instance of: scholarly article
title: Relaxed very asymmetric coloring games
zbMATH Open document ID: 1193.05082
author: Daqing Yang
published in: Discrete Mathematics
publication date: 2009-04-09T00:00:00Z
review text: This paper investigates a competitive version of the coloring game on a finite graph \(G\). An asymmetric variant of the \((r,d)\)-relaxed coloring game is called the \((r,d)\)-relaxed \((a,b)\)-coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph \(G\), using colors from a set \(X\), with \(|X|=r\). On each turn Alice colors \(a\) vertices and Bob colors \(b\) vertices. A color \(\alpha \in X\) is legal for an uncolored vertex \(u\) if by coloring \(u\) with color \(\alpha\), the subgraph induced by all the vertices colored with \(\alpha\) has maximum degree at most \(d\). Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The \(d\)-relaxed \((a,b)\)-game chromatic number, denoted by \((a,b)-\chi^d_X(G)\), of \(G\) is the least \(r\) for which Alice has a winning strategy in the \((r,d)\)-relaxed \((a,b)\)-coloring game. The \((r,d)\)-relaxed \((1,1)\)-coloring game has been well studied and there are many interesting results. For the \((r,d)\)-relaxed \((a,1)\)-coloring game, this paper proves that if a graph \(G\) has an orientation with maximum outdegree \(k\) and \(a \geq k\), then \((a,1)-\chi^d_g(G) \leq k+1\) for all \(d \geq k^2+2k\); If \(a \geq k^3\), then \((a,1)-\chi^d_g(G) \leq k+1\) for all \(d \geq 2k+1\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 5542423
zbMATH Keywords: competitive coloring
zbMATH Keywords: asymmetric coloring game
zbMATH Keywords: relaxed chromatic number
zbMATH Keywords: relaxed game chromatic number
zbMATH Keywords: graph orientation
MaRDI profile type: Publication
full work available at URL: j.disc.2007.11.058
OpenAlex ID: W2030991289
cites work: Q4028100
cites work: Relaxed game chromatic number of graphs
cites work: A simple competitive graph coloring algorithm. II.
cites work: A simple competitive graph coloring algorithm. III
cites work: The relaxed game chromatic number of outerplanar graphs
cites work: Relaxed game chromatic number of trees and outerplanar graphs
cites work: A simple competitive graph coloring algorithm
cites work: Asymmetric graph coloring games
cites work: Very asymmetric marking games
cites work: Q5310233
cites work: Asymmetric marking games on line graphs
cites work: The game coloring number of planar graphs
cites work: The game coloring number of pseudo partial \(k\)-trees
DOI: 10.1016/J.DISC.2007.11.058
Recommended article: Asymmetric graph coloring games
Recommended article: Colouring games
Recommended article: Asymmetric directed graph coloring games
Recommended article: Impartial coloring games
Recommended article: On the relaxed colouring game and the unilateral colouring game
Recommended article: The coloring game on matroids
Recommended article: Activation strategy for relaxed asymmetric coloring games
Recommended article: Q4691913
Recommended article: The orthogonal colouring game
Recommended article: Colored cut games
description: scientific article; zbMATH DE number 5542423