Colourings, homomorphisms, and partitions of transitive digraphs

详细信息    查看全文

• 作者：Tomá ; s Feder^a ; ^{tomas@theory.stanford.edu" class="auth_mail" title="E-mail the corresponding author} ; Pavol Hell^b ; ^{pavol@sfu.ca" class="auth_mail" title="E-mail the corresponding author} ; Cé ; sar Herná ; ndez-Cruz^b ; ^c ; ^{chc@ciencias.unam.mx" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：60
• 期：Complete
• 页码：55-65
• 全文大小：400 K

文摘

We investigate the complexity of generalizations of colourings (acyclic colourings, (k,ℓ)$(k,\ell )$-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.