Colourings, homomorphisms, and partitions of transitive digraphs

DOI10.1016/J.EJC.2016.09.001MaRDI QIDQ338575zbMATHOpenAlexFDO

Authors Tomás Feder, Pavol Hell, César Hernández-Cruz

Publication date 7 November 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.07744

zbMATH Keywords

\((k, \ell)\)-colouringsacyclic colourings

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• On path partitions and colourings in digraphs
• Publication:5753972
• Graph colourings and partitions
• scientific article; zbMATH DE number 4073004
• Colored graph homomorphisms
• A note on coloring vertex-transitive graphs
• Partitions and edge colourings of multigraphs
• scientific article; zbMATH DE number 3974975
• A note on total colourings of digraphs
• Transitive edge coloring of graphs and dimension of lattices

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Berge trigraphs
• Colourings, homomorphisms, and partitions of transitive digraphs
• Digraph girth via chromatic number
• Digraph matrix partitions and trigraph homomorphisms
• Graph partitions with prescribed patterns
• List Partitions
• Matrix partitions of perfect graphs
• Minor‐order obstructions for the graphs of vertex cover 6
• On realizations of point determining graphs, and obstructions to full homomorphisms
• Partitioning graphs into complete and empty graphs
• Properties of vertex cover obstructions
• Quasi‐transitive digraphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of colouring by locally semicomplete digraphs
• The dichromatic number of a digraph
• \(k\)-kernels in generalizations of transitive digraphs

Cited in

(10)

• On the Complexity of Ordered Colorings
• Graph partitions with prescribed patterns
• On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs
• Digraph matrix partitions and trigraph homomorphisms
• Generalization of transitive fraternal augmentations for directed graphs and its applications
• scientific article; zbMATH DE number 7034041 (Why is no real title available?)
• Generalisations of matrix partitions: complexity and obstructions
• The recognition of bound quivers using edge-coloured homomorphisms
• Colourings, homomorphisms, and partitions of transitive digraphs
• Quasi-transitive digraphs and their extensions

This page was built for publication: Colourings, homomorphisms, and partitions of transitive digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q338575)