KAIST Discrete Math Seminar

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.