Colourings and Flows in Graphs

In combinatorial mathematics, a graph is a set of points, some of which may be joined by lines. Graphs are useful models for electrical grids, chemical structures, the internet, transportation maps, and many other objects -- anything that can be viewed as a network is, abstractly, a graph. Real world problems involving such networks benefit from the theorems, algorithms, and insights of graph theory. The PI is most interested in graph problems involving so-called colourings and flows, and this project focuses on three sub-problems within these topics. Graduate students will be mentored as part of this project. The three sub-projects prioritized in this proposal are titled: flows with boundary conditions in graphs; clique subgraphs and strong colouring, and; total colouring and overfullness in graphs with large maximum degree. The first of these is about developing concepts for use as inductive tools towards Tutte's Flow Conjectures. The second is an attack on the Strong Colouring Conjecture, using a clique reduction technique. The third and final sub-project seeks to prove a special case of the Overfull Conjecture (involving large graphs with large maximum degree) and to use this work towards the Total Colouring Conjecture. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.