Graphs Identified by Logics with Counting

DOI10.1145/3417515MaRDI QIDQ5056356zbMATH OpenOpenAlexWikidataFDO

Authors Sandra Kiefer, P. Schweitzer, Erkal Selman

Publication date 8 December 2022

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3417515

zbMATH Keywords

CFI graphscolor refinementcounting quantifiersfirst-order logicinversionWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Logic in computer science (03B70) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Relational systems, laws of composition (08A02) Descriptive complexity and finite models (68Q19)

Recommendations

• Graphs identified by logics with counting
• An optimal lower bound on the number of variables for graph identification
• Counting bounded tree depth homomorphisms
• Canonization for two variables and puzzles on the square
• Logics with counting and equivalence

Cited in

(10)

• Canonization for two variables and puzzles on the square
• Graphs identified by logics with counting
• scientific article; zbMATH DE number 6739879 (Why is no real title available?)
• On the Weisfeiler-Leman dimension of permutation graphs
• On the descriptive complexity of groups without abelian normal subgroups
• On the descriptive complexity of groups without abelian normal subgroups (extended abstract)
• Computational complexity of the Weisfeiler-Leman dimension
• Computational complexity of the Weisfeiler-Leman dimension
• Canonical labeling of sparse random graphs
• Color refinement for relational structures

This page was built for publication: Graphs Identified by Logics with Counting

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