Graph Partitions

Gary MacGillivray

Department of Mathematics and Statistics, University of Victoria, Victoria, B.C. Canada

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.

This is a joint work with Peter Dukes and Steve Lowdon.

Tags: GaryMacGillivray