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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.61--76
Liste complète des métadonnées

https://hal.inria.fr/hal-01188906
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 31 août 2015 - 17:03:28
Dernière modification le : vendredi 1 juin 2018 - 15:24:01
Document(s) archivé(s) le : mardi 1 décembre 2015 - 10:43:02

Fichier

dmtcs-16-3-4.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01188906, version 1

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 (in progress) (3), pp.61--76. 〈hal-01188906〉

Partager

Métriques

Consultations de la notice

58

Téléchargements de fichiers

331