Spieltheoretische Kantenfärbungsprobleme auf Wäldern und verwandte Strukturen

Andres, Dominique (2003) Spieltheoretische Kantenfärbungsprobleme auf Wäldern und verwandte Strukturen. Masters thesis.

Abstract

This diploma thesis discusses graph colouring games, as introduced by Bodlaender [3], in a more general setting. The main results are: The directed and undirected game chromatic indices of the class of forests of maximum degree D are D+1, for D=3, D=5, and D>5. The directed game chromatic indices of the class of forests of maximum degree 2 are 2 or 3, depending on whether passing is allowed for Alice in the underlying game. The method of decomposition of independent subtrees is extended from edge colouring games to node colouring games and leads to new proofs resp. new results concerning the undirected resp. directed (new) game chromatic numbers of the class of forests. These numbers are 4 (3) resp. 3 (3). The results mentioned so far are also true for infinite instead of finite graphs. Some general properties of graph colouring games are examined. A list of important open questions can be found at the end.


Actions:
Download: [img] Postscript - Accepted Version
Download (1MB) | Preview
Download: [img] PDF - Accepted Version
Download (902kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2004-474
Depositing User: Dominique Andres
Date Deposited: 13 Dec 2004 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/474