Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653181 | European Journal of Combinatorics | 2017 | 11 Pages |
Abstract
We investigate the complexity of generalizations of colourings (acyclic colourings, (k,ℓ)(k,ℓ)-colourings, homomorphisms, and matrix partitions), for inputs restricted to the class of transitive digraphs. Even though transitive digraphs are nicely structured, many problems are intractable, and their complexity turns out to be difficult to classify. We present some motivational results and several open problems.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tomás Feder, Pavol Hell, César Hernández-Cruz,