Colourings, homomorphisms, and partitions of transitive digraphs

DOI10.1016/j.ejc.2016.09.001zbMath1348.05073arXiv1510.07744OpenAlexW2256982406MaRDI QIDQ338575

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

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

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

Related Items

Colourings, homomorphisms, and partitions of transitive digraphs ⋮ Graph partitions with prescribed patterns ⋮ Quasi-Transitive Digraphs and Their Extensions

Cites Work

• Unnamed Item
• Colourings, homomorphisms, and partitions of transitive digraphs
• The complexity of colouring by locally semicomplete digraphs
• Digraph matrix partitions and trigraph homomorphisms
• Partitioning graphs into complete and empty graphs
• The dichromatic number of a digraph
• Matrix partitions of perfect graphs
• Properties of vertex cover obstructions
• On realizations of point determining graphs, and obstructions to full homomorphisms
• Graph partitions with prescribed patterns
• Digraph Girth via Chromatic Number
• k-kernels in generalizations of transitive digraphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• List Partitions
• Minor‐order obstructions for the graphs of vertex cover 6
• Quasi‐transitive digraphs
• Berge trigraphs