Gary MacGillivray, Graph Partitions

Graph Partitions
Gary MacGillivray
Department of Mathematics and Statistics, University of Victoria, Victoria, B.C. Canada
2012/11/9 Fri 4PM-5PM
We consider partitions of the vertices of a graph into a fixed number of labelled cells such that (i) the subgraph induced by each cell belongs to a family that depends on the cell, and (ii) edges joining vertices in different cells are allowed only if the cells correspond to adjacent vertices in a given pattern graph H. Both polynomiality and NP-completeness results are presented. Tha focus is on methods that give polynomial time algorithms.
This is a joint work with Peter Dukes and Steve Lowdon.


Comments are closed.