Skipping Turns on the Ordering Game

In the ordering game on a graph G, Alice and Bob take turns placing the vertices of G into a linear ordering. The score of the game is the maximum number of neighbors that any vertex has before it in the ordering. Alice's goal in the ordering game is to minimize the score, while Bob's goal is to maximize it. The game coloring number is the least score that Alice can always guarantee in the ordering game, no matter how Bob plays. This paper examines what happens to the game coloring number if Alice or Bob skip turns on the ordering game. Preliminary definitions and examples are provided to give context to the ordering game. These include a polynomial time algorithm to compute the coloring number, a non-competitive version of the game coloring number. The notion of the preordered game is introduced as the primary tool of the paper, along with its naturally defined preordered game coloring number. To emphasize the complex relationship between the coloring number and the preordered game coloring number, a non-polynomial time strategy is given to Alice and Bob that yields the preordered game coloring number on any graph. Additionally, the preordered game coloring number is shown to be monotonic, one of the most useful properties for turn-skipping. Techniques developed throughout the paper are then used to determine that Alice cannot reduce the score and Bob cannot improve the score by skipping any number of their respective turns. This paper can hopefully be used as a stepping stone towards bounding the score on graphs when vertices are removed, as well as in deciphering further properties of the asymmetric marking game.