Digraph matrix partitions and trigraph homomorphisms

DOI10.1016/j.dam.2006.02.009zbMath1106.05060OpenAlexW2048988825MaRDI QIDQ860407

Kim Tucker-Nally, Tomás Feder, Pavol Hell

Publication date: 9 January 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.02.009

zbMATH Keywords

NP-complete problemsconstraint satisfaction problemspolynomial-time algorithmscomplexity dichotomylist homomorphismsdigraph homomorphismslist matrix partitionsmatrix partition problemstrigraph homomorphisms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (11)

Unnamed Item ⋮ Colourings, homomorphisms, and partitions of transitive digraphs ⋮ Obstructions to partitions of chordal graphs ⋮ Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms ⋮ Colouring, constraint satisfaction, and complexity ⋮ Dichotomy for tree-structured trigraph list homomorphism problems ⋮ Graph partitions with prescribed patterns ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ Adjusted Interval Digraphs ⋮ Matrix Partitions with Finitely Many Obstructions ⋮ List matrix partitions of chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• List matrix partitions of chordal graphs
• On the complexity of H-coloring
• Polynomial graph-colorings
• Homomorphisms of edge-colored graphs and Coxeter groups
• On the algebraic structure of combinatorial problems
• Partitioning chordal graphs into independent sets and cliques
• Stable skew partition problem
• The recognition of bound quivers using edge-coloured homomorphisms
• Complexity of graph partition problems
• Complexity of conservative constraint satisfaction problems
• The Complexity of the List Partition Problem for Graphs
• The Complexity of Colouring by Semicomplete Digraphs
• On the complexity of the general coloring problem
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• List Partitions
• Bi‐arc graphs and the complexity of list homomorphisms
• Full Constraint Satisfaction Problems

This page was built for publication: Digraph matrix partitions and trigraph homomorphisms