Colourings, homomorphisms, and partitions of transitive digraphs
Por:
Feder, Tomas, Hell, Pavol, Hernandez-Cruz, Cesar
Publicada:
1 feb 2017
Resumen:
We investigate the complexity of generalizations of colourings (acyclic colourings, (k,l)-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. © 2016 Elsevier Ltd
Filiaciones:
Feder, Tomas:
268 Waverley St, Palo Alto, CA 94301 USA
Hell, Pavol:
Simon Fraser Univ, Sch Comp Sci, Burnaby, BC V5A 1S6, Canada
Hernandez-Cruz, Cesar:
Simon Fraser Univ, Sch Comp Sci, Burnaby, BC V5A 1S6, Canada
Univ Nacl Autonoma Mexico, Fac Ciencias, Mexico City 04510, DF, Mexico
|