Colourings, Homomorphisms, and Partitions of Transitive Digraphs
Preprint
Abstract
We investigate the complexity of generalizations of colourings (acyclic colourings, $(k,\ell)$-colourings, homomorphisms, and matrix partitions), for 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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden SubgraphsJournal of Graph Theory, 2016
- Graph partitions with prescribed patternsEuropean Journal of Combinatorics, 2014
- Partitioning graphs into complete and empty graphsDiscrete Mathematics, 2009
- On realizations of point determining graphs, and obstructions to full homomorphismsDiscrete Mathematics, 2008
- Properties of vertex cover obstructionsDiscrete Mathematics, 2007
- Digraph matrix partitions and trigraph homomorphismsDiscrete Applied Mathematics, 2006
- Matrix partitions of perfect graphsDiscrete Mathematics, 2006
- Berge trigraphsJournal of Graph Theory, 2006
- Minor‐order obstructions for the graphs of vertex cover 6Journal of Graph Theory, 2002
- Quasi‐transitive digraphsJournal of Graph Theory, 1995