Colouring Graphs with Dr. Russell Campbell

“Dr. Russell Campbell of the UFV School of Computing has had a paper published in the Open Journal of Discrete Mathematics, with co-authors Nancy E. Clarke (Acadia University) and Gary MacGillivray (University of Victoria).

The paper describes work on the problem of graph-colouring. “Most people are familiar with connect-the-dots drawing from their childhood as one of the most basic examples of graphs,” Dr. Campbell said. “Graph colouring can involve the structure of the graph when connections are each given a direction where the colours seen at either end of the connections always keep the direction consistent.

A generalization of this looks at local structure surrounding each node so that assignments of colours are consistent with respect to the structure. This paper describes when it is easy to assign to graphs versus when it is difficult to colour and maintain these consistencies.”

The journal is open-access and the paper can be read or downloaded here.”