Skip to Main content Skip to Navigation
Journal articles

Complexity of conditional colouring with given template

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.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-01188906
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 31, 2015 - 5:03:28 PM
Last modification on : Friday, June 1, 2018 - 3:24:01 PM
Long-term archiving on: : Tuesday, December 1, 2015 - 10:43:02 AM

File

dmtcs-16-3-4.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Peter J. Dukes, Steve Lowdon, Gary Macgillivray. Complexity of conditional colouring with given template. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (3), pp.61--76. ⟨10.46298/dmtcs.2092⟩. ⟨hal-01188906⟩

Share

Metrics

Record views

35

Files downloads

592