文摘
We investigate the complexity of generalizations of colourings (acyclic colourings, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0195669816300786&_mathId=si4.gif&_user=111111111&_pii=S0195669816300786&_rdoc=1&_issn=01956698&md5=023982b792df4f65b3812024699bc5c0" title="Click to view the MathML source">(k,ℓ)class="mathContainer hidden">class="mathCode">-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.