Cover Image

Graph classes through the lens of logic

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Pilipczuk, Michał
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Discrete Mathematics Data Structures and Algorithms Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)

Coarse Balanced Separators in Fat-Minor-Free Graphs
by: Bonnet, Édouard, et al.
Published: (2026)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

On merge-models
by: Buffière, Hector, et al.
Published: (2026)

Merge-width and First-Order Model Checking
by: Dreier, Jan, et al.
Published: (2025)

On classes of bounded tree rank, their interpretations, and efficient sparsification
by: Gajarský, Jakub, et al.
Published: (2024)

Redundancy Is All You Need (for CSP Sparsification)
by: Brakensiek, Joshua, et al.
Published: (2024)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
by: Grohe, Martin, et al.
Published: (2023)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
by: Marx, Dániel, et al.
Published: (2026)

Variants of Merge-Width and Applications
by: Drabik, Karolina, et al.
Published: (2026)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
by: Lyon, Tim S., et al.
Published: (2023)

Solving Partial Dominating Set and Related Problems Using Twin-Width
by: Balabán, Jakub, et al.
Published: (2025)

Formal Primal-Dual Algorithm Analysis
by: Abdulaziz, Mohammad, et al.
Published: (2026)

Color Refinement for Relational Structures
by: Scheidt, Benjamin, et al.
Published: (2024)

The Iteration Number of the Weisfeiler-Leman Algorithm
by: Grohe, Martin, et al.
Published: (2023)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
by: Koh, Zhuan Khye, et al.
Published: (2021)

SDPs and Robust Satisfiability of Promise CSP
by: Brakensiek, Joshua, et al.
Published: (2022)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
by: Majewski, Konrad, et al.
Published: (2022)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
by: Černý, Marek
Published: (2026)

SAT Encoding of Partial Ordering Models for Graph Coloring Problems
by: Faber, Daniel, et al.
Published: (2024)

First-order transducibility among classes of sparse graphs
by: Gajarský, Jakub, et al.
Published: (2025)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
by: Bourneuf, Romain, et al.
Published: (2025)

EPTAS for Hard Graph Cut Problems for Dense Graphs
by: Deguchi, Kaisei, et al.
Published: (2026)

Extending Ghouila-Houri's Characterization of Comparability Graphs to Temporal Graphs
by: Charbit, Pierre, et al.
Published: (2025)

3D-grids are not transducible from planar graphs
by: Gajarský, Jakub, et al.
Published: (2025)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
by: Černý, Marek, et al.
Published: (2025)

Smaller Circuits for Bit Addition
by: Goncharov, Mikhail, et al.
Published: (2025)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)

Colouring Probe $H$-Free Graphs
by: Paulusma, Daniël, et al.
Published: (2025)

$α_i$-Metric Graphs: Hyperbolicity
by: Dragan, Feodor F., et al.
Published: (2024)

Palette Sparsification for Graphs with Sparse Neighborhoods
by: Dhawan, Abhishek
Published: (2024)

Separability Properties of Monadically Dependent Graph Classes
by: Bonnet, Édouard, et al.
Published: (2025)

Light Edge Fault Tolerant Graph Spanners
by: Bodwin, Greg, et al.
Published: (2025)

Bounding Width on Graph Classes of Constant Diameter
by: Dabrowski, Konrad K., et al.
Published: (2025)

Sandwich Monotonicity and the Recognition of Weighted Graph Classes
by: Beisegel, Jesse, et al.
Published: (2025)

Graph parameters that are coarsely equivalent to path-length
by: Dragan, Feodor F., et al.
Published: (2025)

Hardness of Burning Number Problem on Regular Graphs
by: Antony, Dhanyamol, et al.
Published: (2026)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
by: Holtgrefe, Niels, et al.
Published: (2024)