Logical equivalences, homomorphism indistinguishability, and forbidden minors

DOI10.4230/LIPICS.MFCS.2023.82MaRDI QIDQ6647722zbMATH OpenFDO

Authors Tim Seppelt

Publication date 3 December 2024

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2023.82

zbMATH Keywords

graph minorhomomorphism indistinguishabilitylogic

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(10)

• Limitations of game comonads for invertible-map equivalence via homomorphism indistinguishability
• Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
• On homomorphism indistinguishability and hypertree depth
• Homomorphism-distinguishing closedness for graphs of bounded tree-width
• The complexity of homomorphism reconstructibility
• Monotonicity of the cops and robber game for bounded depth treewidth
• An algorithmic meta theorem for homomorphism indistinguishability
• Homomorphism counts to trees
• Color refinement for relational structures
• NPA hierarchy for quantum isomorphism and homomorphism indistinguishability

This page was built for publication: Logical equivalences, homomorphism indistinguishability, and forbidden minors

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