| HAL-Inria | Publications, software ... of Inria's scientists |
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.
https://hal.inria.fr/hal-01188906
Contributor : Coordination Episciences Iam <>
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
Contributor : Coordination Episciences Iam <>
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