The complexity of the matroid homomorphism problem

DOI10.37236/11119zbMATH Open1516.05021MaRDI QIDQ6162136FDOQ6162136

Authors: Cheolwon Heo, Hyobin Kim, Siggers Mark 

Publication date: 15 June 2023

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Recommendations

• A note on maxflow-mincut and homomorphic equivalence in matroids
• Complexity of tree homomorphisms
• On the complexity of matroid isomorphism problem
• On the Complexity of Matroid Isomorphism Problems
• scientific article; zbMATH DE number 878894

zbMATH Keywords

binary matroidmatroid homomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• On the complexity of H-coloring
• 2-Isomorphic Graphs
• List homomorphisms to reflexive graphs
• Bi‐arc graphs and the complexity of list homomorphisms
• Testing Linear-Invariant Non-Linear Properties
• A Proof of the CSP Dichotomy Conjecture

Cited In (5)

• On the Complexity of Some Enumeration Problems for Matroids
• Matroid Complexity and Nonsuccinct Descriptions
• On the Complexity of Matroid Isomorphism Problems
• On the complexity of matroid isomorphism problem
• A note on maxflow-mincut and homomorphic equivalence in matroids

This page was built for publication: The complexity of the matroid homomorphism problem

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