Skip to main content Accessibility help
×
Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T03:43:25.333Z Has data issue: false hasContentIssue false

14 - Colouring games

Published online by Cambridge University Press:  05 May 2015

Zsolt Tuza
Affiliation:
University of Pannonia
Xuding Zhu
Affiliation:
University in mainland China
Lowell W. Beineke
Affiliation:
Purdue University, Indiana
Robin J. Wilson
Affiliation:
The Open University, Milton Keynes
HTML view is not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Summary

There are various kinds of two-person games in which the players construct a colouring of a graph (or of a subgraph), and some additional games are closely related to graph colourings. Here we describe several variants, most of which deal with ‘maker–breaker games’. We also consider the game version of list-colourings.

Introduction

The connection between graph colourings and game theory has its roots in the works of P. M. Grundy in the latter field as early as the 1930s. His research later motivated the introduction of some graph invariants, one of which is discussed in detail in Berge's monograph [9]. For undirected graphs the analogous parameter is the Grundy number, also called the online chromatic number, which we will consider in Section 9. But although Grundy colouring may be formulated in terms of games, it remains a solitaire game in which the player aims at finding a solution that is as bad as possible.

In this chapter we mainly consider non-cooperative two-person games that either construct colourings or are otherwise closely related to some kind of colouring concept, even when they do not colour the graph.

A good starting point is the following maker–breaker game, which was introduced by Brams [24] for planar graphs in 1981, and independently by Bodlaender [12] for general graphs in 1991. Given a graph G, two players alternately colour vertices of G from a set of colours, say {1, 2, …, k}. The two players are Alice (the maker) and Bob (the breaker); each of them colours one uncoloured vertex at a time, under the condition that monochromatic edges must not occur, Alice moving first. Alice wins if a proper k-colouring of the entire graph G is eventually obtained, whereas Bob wins if a situation is reached where the neighbourhood of some uncoloured vertex contains all the k colours of the palette. Certainly, if the number of colours is sufficiently large (for example, if k = |V(G)|), then Alice surely wins the game.

Information

Save book to Kindle

To save this book to your Kindle, first ensure no-reply@cambridge.org is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×