Graph theory

How to catch legendary Pokémon (in practice)

Pokémon Gold and Silver's roaming legendary beasts move randomly from route to route instead of sticking to a fixed habitat. By analyzing their behaviour using the math of random walks on graphs, I can finally answer a question that's bugged me since childhood: what's the best strategy to find a roaming Pokémon as quickly as possible?

A submodular measure and approximate Gomory–Hu theorem for packing odd trails

This paper, published after I left academia, explores the "perimeter" measure that plays a key role in my doctoral research.

Odd disjoint trails and totally odd graph immersions

I have succesfully defended my PhD thesis! It's "packed" with results on graph immersions with parity restrictions, and "covers" odd edge-connectivity, totally odd clique immersions, and a new submodular measure that's intimately connected with both.

Weak duality for packing edge-disjoint odd trails

This paper, coauthored with my supervisor Bojan Mohar and colleague Hehui Wu, was the first entry in my doctoral research into graph immersions with parity restrictions.

On the polarity and monopolarity of graphs

This is my favourite paper to come out of my research with Jing Huang at the University of Victoria, and the last one to be published. The main result is that the structure of monopolar partitions in claw-free graphs can be fully understood by looking at small subgraphs and following their direct implications on vertex pairs.

Solving partition problems with colour-bipartitions

This paper was the culmination of my undergraduate research on monopolar graphs with Jing Huang. It shows that a single strategy can be used to solve the monopolar partition problem in all graph classes for which the problem was previously known to be tractable.

On graph-transverse matchings

I have successfully defended my master’s thesis on graph-transverse matching problems! It considers the computational complexity of deciding whether a given graph admits a matching which covers every copy of a fixed tree or cycle.

Colonialism and the 4-Colour Theorem

In 1852, then-student Francis Guthrie wondered any if possible map required more than four colours. By the end of the century, Guthrie and his fellow colonists had drawn a map on Africa that needed five.

How to catch legendary Pokémon (in theory)

Pokémon Gold and Silver introduced the roaming legendary beasts: three one-of-a-kind Pokémon that move from route to route instead of sticking to a fixed habitat.

Catching a roaming Pokémon amounts to winning a graph pursuit game — so what can we learn about it from the latest mathematical results?

Complexity of cycle-transverse matching problems

This paper by me, Jing Huang, and Xuding Zhu, gives the first results of what would become my master’s thesis. It studies the computational complexity of the following problem: in a given graph, is there a matching which breaks all cycles of a given length?

List-monopolar partitions of claw-free graphs

Shortly after solving the monopolar partition problem for line graphs, Jing and I realized that our solution could be used to solve the "precoloured" version of the problem, and then further extended to claw-free graphs.

Line-polar graphs: characterization and recognition

This paper is the result of the research term I took as an undergraduate in the summer of 2009. It studies the edge versions of the monopolar and polar partition problems, and presents a linear-time solution to both.

The monopolar partition problem in restricted graph classes

A graph is called monopolar if its vertices can be partitioned into an independent set and a disjoint union of cliques. My undergraduate research with Jing Huang studied monopolar partitions in line graphs, claw-free graphs, and other graph classes.

K_n

:
bluest Hamilton circuit
lies fully in

G

Brooks' Theorem tanka

Greedily colour,
ensuring neighbours follow
all except the last.

Choose the last vertex wisely:
friend of few or of leaders.