Peter J. Dukes ; Steve Lowdon ; Gary Macgillivray - Complexity of conditional colouring with given template

dmtcs:2092 - Discrete Mathematics & Theoretical Computer Science, June 19, 2014, Vol. 16 no. 3 - https://doi.org/10.46298/dmtcs.2092
Complexity of conditional colouring with given templateArticle

Authors: Peter J. Dukes 1; Steve Lowdon 1; Gary Macgillivray 2,1

  • 1 Department of Mathematics and Statistics
  • 2 Department of Computer Science [Victoria]

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.

https://doi.org/10.46298/dmtcs.2092
Source: HAL:hal-01188906v1
Volume: Vol. 16 no. 3
Section: Graph Theory
Published on: June 19, 2014
Submitted on: November 14, 2012
Keywords: graph colouring,homomorphism,vertex partitions,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Share and export

Consultation statistics

This page has been seen 465 times.
This article's PDF has been downloaded 610 times.