Category Archives: Graph Theory

Partizen Graph Coloring

Partizen Graph Coloring Game has two players: Alice and Bob. The players alternate coloring the uncolored vertices of a finite graph G from a fixed finite set of colors. At each step of the game, the players must choose to color an uncolored vertex with a legal color. In the basic formation of the game, a color is legal for an uncolored vertex if the vertex has no neighbors already colored with that color. Alice wins the game if all vertices of the graph are colored; otherwise, Bob wins. The least  such that Alice has a winning strategy for this game on \(G\) is called the game chromatic number of G. If the definition of legal color is altered so that at each step in the game, each color class must have maximum degree at most \(d\), for some fixed integer \(dge{0}\), then the least such that Alice has a winning strategy is called the \(d\)-relaxed game chromatic number of \(G\). These parameters have been studied extensively for many classes of graphs. The classes for which the most is known are trees and forests. While upper bounds on the game chromatic number (and \(d\)-relaxed game chromatic number) are known for these classes, and the bounds are known to be achievable, it is not known what structural properties the graphs must have in order to achieve the bounds. This project will attempt to find these properties, thereby classifying these classes completely with respect to the Partizen Graph Coloring Game. We will then attempt to classify trees and forests relative to the d-relaxed game chromatic number for small values of \(d\). Finally, we may consider other variations of the game in which the definition of legal color is altered in other ways.

Foxes and Hares

In the game of Foxes and Hares, we begin with \(k\) foxes, \(F_1, F_2, …, F_k\) and one hare \(H\).  Given a finite undirected graph \(G\), the foxes are first placed at \(k\) vertices of the graph, then the Hare is placed on a vertex.  The foxes and the hare alternate turns.  On the foxes’ turn, each fox may move to an adjacent vertex or remain in place, and multiple foxes may occupy the same vertex.  The hare has the same choices of moves on its turn.

graph1

The foxes win if they catch the hare, meaning there is some time at which a fox occupies the same vertex as the hare; otherwise the hare wins.  For a given graph, the minimum number of foxes required to catch the hare (regardless of the hare’s strategy) is called the graph’s fox number.

How can you find the fox number of a given graph?  What are all of the one-fox graphs?  What characteristic(s) of a graph determine(s) whether or not more than one fox is needed?  What are all of the two-fox graphs?

Pass the Stone

In the game of passing stones, each vertex on a graph begins with a certain number of stones.   On each move, if a vertex has at least as many stones as its degree, it passes one stone to each adjacent vertex.  All vertices pass stones simultaneously.   Initially, we consider only cycle graphs, but you will want to branch out into other kinds of graphs later.

graph1

The Leaves are Gold

Each vertex in a tree is assigned a positive integer value.  Two players take turns deleting a leaf of the remaining tree and adding the value of the leaf to their collection.  The player with the largest value at the end of the game wins.  For what trees and values is this game solvable and what strategies should the first and second players use?

Positive Triangle Game

Two players take turns marking the edges of a complete graph \(K_n\) , for some \(n\), with + or -signs.   The two players can choose either mark (this is known as a choice game).   In Positive Triangle, the first player to complete a triangle with an even number of – signs is the winner.  In this game, the goal or winning triangle can contain marks made by both players.

  1. Under what conditions does the first player win?
  2. If the first player to create a positive triangle loses, under what conditions does the first player win?
  3. For which complete graphs is a draw (no winner) possible

positivetriange