The C_k-extended graft construction

DOI10.1016/J.DAM.2011.04.006MaRDI QIDQ2275937zbMATH OpenOpenAlexFDO

Authors 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

\(\underline X\) enumeration\(\underline X\)-graft constructiondigraph homomorphismpolynomial algorithm

Mathematics Subject Classification ID

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

Recommendations

• A Polynomial Algorithm for Homomorphisms to Oriented Cycles
• scientific article; zbMATH DE number 1996252
• The dichotomy of minimum cost homomorphism problems for digraphs
• The complexity of colouring by locally semicomplete digraphs
• Polynomial graph-colorings

Cites work

• Adjusted interval digraphs
• Classifying the Complexity of Constraints Using Finite Algebras
• Colouring, constraint satisfaction, and complexity
• Duality and Polynomial Testing of Tree Homomorphisms
• Existence theorems for weakly symmetric operations
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 866665 (Why is no real title available?)
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• Minimum cost homomorphisms to semicomplete multipartite digraphs
• On the algebraic structure of combinatorial problems
• On the Structure of Polynomial Time Reducibility
• Polynomial graph-colorings
• The complexity of colouring by locally semicomplete digraphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The dichotomy of list homomorphisms for digraphs
• The effect of two cycles on the complexity of colourings by directed graphs
• Weak near-unanimity functions and digraph homomorphism problems

Cited in

(2)

• Oriented incidence colourings of digraphs
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2275937)