✦ LIBER ✦

Asymmetric graph coloring games

✍ Scribed by H. A. Kierstead

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 151 KB
Volume: 48
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20049

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We introduce the (a,b)‐coloring game, an asymmetric version of the coloring game played by two players Alice and Bob on a finite graph, which differs from the standard version in that, in each turn, Alice colors a vertices and Bob colors b vertices. We also introduce a related game, the (a,b)‐marking game. We analyze these games and determine the (a,b)‐chromatic numbers and (a,b)‐coloring numbers for the class of forests and all values of a and b. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 169–185, 2005

📜 SIMILAR VOLUMES

Game coloring the Cartesian product of g

Game coloring the Cartesian product of graphs

✍ Xuding Zhu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB

## Abstract This article proves the following result: Let __G__ and __G__′ be graphs of orders __n__ and __n__′, respectively. Let __G__^\*^ be obtained from __G__ by adding to each vertex a set of __n__′ degree 1 neighbors. If __G__^\*^ has game coloring number __m__ and __G__′ has acyclic chromat

The Game Coloring Number of Planar Graph

The Game Coloring Number of Planar Graphs

✍ Xuding Zhu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 121 KB

This paper discusses a variation of the game chromatic number of a graph: the game coloring number. This parameter provides an upper bound for the game chromatic number of a graph. We show that the game coloring number of a planar graph is at most 19. This implies that the game chromatic number of a

Graph Coloring and Reverse Mathematics

✍ James H. Schmerl 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB

Scalable parallel graph coloring algorit

Scalable parallel graph coloring algorithms

✍ Gebremedhin, Assefaw Hadish ;Manne, Fredrik 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB 👁 1 views

A note concerning asymmetric games on gr

A note concerning asymmetric games on graphs

✍ Alvin E. Roth 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB

## Abstract We consider a class of asymmetric two‐person games played on graphs, and characterize all the positions in the game.

Parallel and On-Line Graph Coloring

✍ Magnus M Halldórsson 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 209 KB

We discover a surprising connection between graph coloring in two orthogonal paradigms: parallel and on-line computing. We present a randomized on-line Ž . coloring algorithm with a performance ratio of O nrlog n , an improvement of log n factor over the previous best known algorithm of Vishwanathan