摘要

圖的著色是在圖論中令人著迷的研究領域之一，當中有很多富挑戰性的 問題、富深度的結果和一些精煉的工具。最出名的結果是四色定理： 可以用四 種顏色去填一張地圖， 使得相鄰的國家填上不同的顏色。在這次演講中， 我們 考慮一個變種的著色問題： 以遊戲方式去著色。首先取定一幅地圖和一些顏 色。兩名參賽者Alice和Bob，他們輪流在地圖上為各個國家著色，我們的要求是 鄰國必須填上不同的顏色。若果整幅地圖都能填滿顏色， 則Alice贏得了比賽。 反之，即有一個國家是無法填色，則Bob贏了。問題是至少需要多少種顏色可令 Alice有必勝策略。我會闡述研究這問題的一些工具和它的發展。

 

Abstract

Graph coloring is a fascinating research area in graph theory, with many challenging open problems, deep results and sophiscated tools. The most well-known result is the Four Color Theorem: In every map, the countries (connected regions in the plane) can be colored with four colors so that any two neighboring countries have distinct colors. In this talk, we consider a variation of the coloring problem: a coloring produced through a game. Take an arbitrary map and a set of colors. Two players, Alice and Bob, alternate their turns in coloring the countries, subject to the constraint that neighboring countries must be assigned distinct colors. Alice wins the game if eventually every country is coloured, and Bob win if there is a country uncoloured but all the colors have been used by its neighboring countries. The problem is how many colors are needed for Alice to have a winning strategy. I shall explain some tools used in the study of this problem, and survey development in this area.