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 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).

  • 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, is there exists a game X such that G:X is not equal to H:X? (an unpublished 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? If so this would imply the cop number and attacking cop number can be arbitrarily far apart (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)

  • 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) (see here)

  • 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 (see here for more).