Research

Interests:

My current focus is pure mathematics problems in graph theory, many of which have practical applications in computer science. A short survey of these include,

  • Graph colouring/homomorphisms,

  • Graphs with forbidden minors,

  • Graphs with forbidden subgraphs or forbidden induced subgraphs,

  • Deterministic discrete time process and pursuit evasion games,

  • Combinatorial games and their corresponding graphs, and

  • The existence of short synchronising words in deterministic finite automata.

Going forward I aim to incorporate more extremal and algebraic tools into my research. I am also interested in incorporating more computer assistance in my work, especially for gaining intuition and intelligently searching for counter-examples. Outside of this I am always on the lookout for more skills and tools that will improve the quality of my work.

If you are interested in collaborating or are otherwise interested in my work, feel free to contact me.

Open Problems (I enjoy):

The following are some of the open problems I enjoy.

  • The cop number of every graph of order n is O(n^{1/2}) (Meyneil’s conjecture).

  • Does every deterministic finite automata of order n admitting a synchronising word contain a synchronising word of length at most (n-1)^2 (Černy’s conjecture).

  • Can the winner of a position in CHOMP be decided in polynomial time?

  • Does every connected vertex transitive graph contain a Hamilton path? (Lovász’s conjecture)

  • Does every bipartite, 3-connected, cubic, planar graph contain a Hamilton Cycle? (Barnette’s conjecture)

  • There exists a function f satisfying; if G is a graph such that every odd cycle of G spans a subgraph with chromatic number at most k, then G has chromatic number at most f(k) (an old conjecture of Erdős and Hajnal)

  • Let D = (V,E), be a digraph. A 2-kernel (quasi-kernal) K is an independent set of D that satisfies for all v in V, there exists a u in K such that dist(u,v) <= 2. In 1976 Erdős and Székely conjectured that every sourceless n vertex digraph contains a 2-kernel of order at most n/2.