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 (particularly for oriented graphs),
The topological structure of graphs embedded of surfaces of bounded Euler genus,
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 spectral/algebraic tools and problems into my research program. Outside of this I am always on the lookout for more skills and tools that will improve the quality of my work.
If you have any suggestions for how I can better my research or expand its scope (in a natural way) feel free to contact me.
Open Problems (I enjoy):
The following are some of the open problems I have failed to solve, but seem worth solving. This list is not comprehensive and not all the problems on it are created equal. I imagine I will edit this list, perhaps significantly, on occasion. Feel free to share any progress you make on these problems.
The cop number of every graph of order n is O(n^{1/2}) (Meyneil’s conjecture, see here).
What is the smallest constant k such that every oriented planar graph has an oriented k-colouring (the planar oriented colouring problem, see here).
What is the smallest constant k such that every graph with Euler genus at most g has a O(g^k)-colouring (see here).
Can the eternal distance-k domination number of trees be calculated in linear time for k > 2? (see here and here).
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, see here).
Can the winner of a position in CHOMP be decided in polynomial time? (see here)
If G and H are combinatorial games which are not equivalent modulo domination, then there exists a game X such that G:X is not equal to H:X. (an published conjecture, see here for background)
Does every connected vertex transitive graph contain a Hamilton path? (Lovász’s conjecture, see here)
Does every bipartite, 3-connected, cubic, planar graph contain a Hamilton Cycle? (Barnette’s conjecture, see here)
Does there exists a d-regular graph G=(V,E) with girth at least 9, such that G^2-E has cop number at most 2d-k for arbitrarily large k? (an unpublished problem I encountered, if so this would result in a surprising theorem)
What is the largest order of an oriented-clique of Euler genus g? (see here)
Let a_1,…,a_k be any set of real numbers. If A is a set of n real numbers, then there exists subset of B of A of size cn for some constant c which depends only on k , such that for all x_1,…,x_k in B the sum of a_i times x_i for all i is not in B (a natural generalisation of Erdős’ sum free set theorem see Chapter.1.4 here)