The \(C_{k}\)-extended graft construction

DOI10.1016/j.dam.2011.04.006zbMath1223.05300MaRDI QIDQ2275937

Gary MacGillivray, Jacobus Swarts

Publication date: 10 August 2011

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

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

zbMATH Keywords

polynomial algorithm; digraph homomorphism; \(\underline X\) enumeration; \(\underline X\)-graft construction

Mathematics Subject Classification ID

05C31: Graph polynomials

05C30: Enumeration in graph theory

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colouring, constraint satisfaction, and complexity
• The complexity of colouring by locally semicomplete digraphs
• The effect of two cycles on the complexity of colourings by directed graphs
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• Existence theorems for weakly symmetric operations
• Polynomial graph-colorings
• On the algebraic structure of combinatorial problems
• Weak near-unanimity functions and digraph homomorphism problems
• Adjusted Interval Digraphs
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Duality and Polynomial Testing of Tree Homomorphisms
• Classifying the Complexity of Constraints Using Finite Algebras