Graphs Identified by Logics with Counting

DOI10.1007/978-3-662-48057-1_25zbMath1465.68101arXiv1503.08792OpenAlexW1809739516MaRDI QIDQ2946347

Sandra Kiefer, Pascal Schweitzer, Erkal Selman

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.08792

Mathematics Subject Classification ID

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

Related Items (10)

Graph isomorphism, color refinement, and compactness ⋮ Graphs Identified by Logics with Counting ⋮ On Tinhofer’s Linear Programming Approach to Isomorphism Testing ⋮ On the Power of Color Refinement ⋮ The Weisfeiler-Leman dimension of distance-hereditary graphs ⋮ Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic ⋮ Unnamed Item ⋮ The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw ⋮ On Weisfeiler-Leman invariance: subgraph counts and related graph properties ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal lower bound on the number of variables for graph identification
• Canonization for two variables and puzzles on the square
• Logical hierarchies in PTIME
• On logics with two variables
• Practical graph isomorphism. II.
• Complexity of the two-variable fragment with counting quantifiers
• Sherali--Adams Relaxations and Indistinguishability in Counting Logics
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Graphs Identified by Logics with Counting
• On the Power of Color Refinement
• Pebble Games with Algebraic Rules
• On the Uniqueness of the Triangular Association Scheme
• Random Graph Isomorphism
• Finite Variable Logics in Descriptive Complexity Theory
• Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth
• Pebble Games and Linear Equations
• Regular Graphs and the Spectra of Two-Variable Logic with Counting

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