Complexity of conditional colouring with given template

Graph Theory 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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2014-11, Vol.16 no. 3 (Graph Theory), p.61-76
Main Authors: Dukes, Peter J., Lowdon, Steve, Macgillivray, Gary
Format: Article
Language:English
Subjects:
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
Computer Science
Discrete Mathematics
graph colouring
homomorphism
vertex partitions
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph Theory 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.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.2092