Full metadata
Title
Skipping Turns on the Ordering Game
Description
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.
Date Created
2019-05
Contributors
- Guglielmo, Jason A (Author)
- Kierstead, Henry (Thesis director)
- Czygrinow, Andrzej (Committee member)
- School of Molecular Sciences (Contributor)
- School of Mathematical and Statistical Sciences (Contributor)
- Barrett, The Honors College (Contributor)
Topical Subject
Resource Type
Extent
24 pages
Language
eng
Copyright Statement
In Copyright
Primary Member of
Series
Academic Year 2018-2019
Handle
https://hdl.handle.net/2286/R.I.52561
Level of coding
minimal
Cataloging Standards
System Created
- 2019-04-17 12:00:37
System Modified
- 2021-08-11 04:09:57
- 3 years 2 months ago
Additional Formats