Conditional Colourings with Given Template
Peter Dukes, Steve Lowdon, Gary MacGillivray
Abstract
We study partitions of the vertex set of a given graph into cells that
each induce a subgraph in a given family, and for which edges can have
ends in different cells only when those cells correspond to adjacent
vertices of a fixed template graph H. For triangle-free
templates, a general collection of graph families for which the
partitioning problem can be solved in polynomial time is
described. For templates with a triangle, the problem is in some cases
shown to be NP-complete.
Full Text: PDF PostScript