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

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

Jacobus Swarts, Gary MacGillivray

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 algorithmdigraph homomorphism\(\underline X\) enumeration\(\underline X\)-graft construction

Mathematics Subject Classification ID

Graph polynomials (05C31) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Oriented incidence colourings of digraphs ⋮ Unnamed Item

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

This page was built for publication: The \(C_{k}\)-extended graft construction