Open Access Te Herenga Waka-Victoria University of Wellington
thesis_access.pdf (502.31 kB)

Adversarial and Online Algorithms

Download (502.31 kB)
posted on 2022-07-10, 11:18 authored by Askes, Matthew

In this thesis we explore a variety of online and adversarial algorithms. We primarily explore the following online and adversarial algorithms; the perfect code game, adversarial online colouring, the chain decomposition game, and strongly online graphs.

The perfect code game is a new adversarial game played on graphs in which players take turns constructing perfect codes. We provide definitions for perfect codes and the perfect code game, along with some motivation from coding theory. We will prove upper bounds for both cycle and path graphs. We also prove an upper bound for graphs of bounded pathwidth. Finally, we explore the perfect code game in graphs of bounded degree.

We will create a new game called the adversarial online colouring game, this game takes elements from both online and adversarial algorithms. We will begin with some discussion and a definition of adversarial online colouring. We will then prove several results related to graph degree. We conclude with a proof that the adversarial online colouring game on trees is determined only by the number of colours and the number of vertices (assuming that both players have a chance at winning).

The chain decomposition game is another adversarial game, but this time played on partial orders. We introduce the chain decomposition game and demonstrate two results relating to upper and lower bounds for the game. We also prove a result on the online adversarial version of the game.

We introduce strongly online graphs and graph colouring as a new algorithmic parameterization to online graph colouring. A strongly online graph is an online graph where at each stage 𝑠 we can see a ball of increasing radius about each vertex. We will prove several bounds (upper and lower) on the online chromatic number of strongly online graphs. For example, we show that every strongly online graph can be coloured in twice its chromatic number. We prove that every strongly online graph with even pathwidth 𝑘 can be online coloured with 2𝑘 + 1 colours. Then, after introducing a natural notion of strongly online pathwidth, we prove that there is a strongly online graph with no finite strongly online path decomposition.


Copyright Date


Date of Award



Te Herenga Waka—Victoria University of Wellington

Rights License

Author Retains Copyright

Degree Discipline


Degree Grantor

Te Herenga Waka—Victoria University of Wellington

Degree Level


Degree Name

Master of Science

ANZSRC Socio-Economic Outcome code

280118 Expanding knowledge in the mathematical sciences; 280115 Expanding knowledge in the information and computing sciences

ANZSRC Type Of Activity code

1 Pure basic research

Victoria University of Wellington Item Type

Awarded Research Masters Thesis



Victoria University of Wellington School

School of Mathematics and Statistics


Downey, Rod