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)