Colourings, homomorphisms, and partitions of transitive digraphs

DOI10.1016/J.EJC.2016.09.001zbMATH Open1348.05073arXiv1510.07744OpenAlexW2256982406MaRDI QIDQ338575FDOQ338575

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Digraph girth via chromatic number
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Berge trigraphs
• The dichromatic number of a digraph
• Quasi‐transitive digraphs
• List Partitions
• Partitioning graphs into complete and empty graphs
• 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
• \(k\)-kernels in generalizations of transitive digraphs
• Colourings, homomorphisms, and partitions of transitive digraphs
• Minor‐order obstructions for the graphs of vertex cover 6
• The complexity of colouring by locally semicomplete digraphs
• Digraph matrix partitions and trigraph homomorphisms

Cited In (10)

• Graph partitions with prescribed patterns
• Generalisations of matrix partitions: complexity and obstructions
• Generalization of transitive fraternal augmentations for directed graphs and its applications
• Title not available (Why is that?)
• On the Complexity of Ordered Colorings
• Quasi-Transitive Digraphs and Their Extensions
• Colourings, homomorphisms, and partitions of transitive digraphs
• Digraph matrix partitions and trigraph homomorphisms
• The recognition of bound quivers using edge-coloured homomorphisms
• On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs

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)