Canonisation and definability for graphs of bounded rank width

DOI10.5555/3470152.3470180MaRDI QIDQ6654493zbMATH OpenFDO

Authors Martin Grohe, Daniel Neuen

Publication date 19 December 2024

Full work available at URL https://doi.org/10.5555/3470152.3470180

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Descriptive complexity and finite models (68Q19)

Cited in

(5)

• Canonization for bounded and dihedral color classes in choiceless polynomial time
• The iteration number of colour refinement
• On the descriptive complexity of groups without abelian normal subgroups (extended abstract)
• Choiceless polynomial time with witnessed symmetric choice
• Logarithmic Weisfeiler-Leman identifies all planar graphs

This page was built for publication: Canonisation and definability for graphs of bounded rank width

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