Cover Image

Courcelle's Theorem: A Self-Contained Proof and a Path-Width Variant

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Rettich, Adrian
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Logic
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A weak variant of Hindman's Theorem stronger than Hilbert's Theorem
by: Carlucci, Lorenzo
Published: (2016)

A Concise Proof of the $L_0$ Dichotomy
by: Matos-Wiederhold, Tonatiuh
Published: (2026)

Roman Domination on Graphings
by: Rettich, Adrian
Published: (2024)

Simple Models of Randomization and Preservation Theorems
by: Khanaki, Karim, et al.
Published: (2024)

Measurable Brooks's Theorem for Directed Graphs
by: Higgins, Cecelia
Published: (2024)

Hall's Harem Theorem with controlled sizes of cycles
by: Duda, Karol
Published: (2025)

New bounds on the strength of some restrictions of Hindman's Theorem
by: Carlucci, Lorenzo, et al.
Published: (2017)

"Weak yet strong" restrictions of Hindman's Finite Sums Theorem
by: Carlucci, Lorenzo
Published: (2016)

Advances in Algorithmic Meta Theorems
by: Siebertz, Sebastian, et al.
Published: (2024)

Projective Chromatic Numbers
by: Rettich, Adrian, et al.
Published: (2026)

A Formal Proof of R(4,5)=25
by: Gauthier, Thibault, et al.
Published: (2024)

Polynomials as terms and the Boolean Independence Theorem
by: Klazar, M.
Published: (2024)

Courcelle's Theorem Without Logic
by: Filmus, Yuval, et al.
Published: (2025)

First-Order Logic and Twin-Width for Some Geometric Graphs
by: Geniet, Colin, et al.
Published: (2025)

Partitioning Theorems for Sets of Semi-Pfaffian Sets, with Applications
by: Lotz, Martin, et al.
Published: (2024)

A computable version of Hall's Harem Theorem and Geometric von Neumann Conjecture
by: Duda, Karol
Published: (2021)

Composition Direction of Seymour's Theorem for Regular Matroids -- Formally Verified
by: Dvorak, Martin, et al.
Published: (2025)

Stable functions and Følner's Theorem
by: Conant, Gabriel
Published: (2024)

An Introduction to Razborov's Flag Algebra as a Proof System for Extremal Graph Theory
by: Jeong, Gyeongwon, et al.
Published: (2026)

Borel Vizing's Theorem for Graphs of Subexponential Growth
by: Bernshteyn, Anton, et al.
Published: (2023)

The strength of Ramsey Theorem for coloring relatively large sets
by: Carlucci, Lorenzo, et al.
Published: (2012)

On a conjecture of Terry and Wolf
by: Gladkova, V.
Published: (2024)

A survey on big Ramsey structures
by: Hubička, Jan, et al.
Published: (2024)

A note on quantitative stability in Hilbert spaces
by: Jing, Yifan
Published: (2026)

A note on measure-theoretic domatic partitions
by: Hou, Edward
Published: (2022)

A new perspective on semi-retractions and the Ramsey property
by: Bartošová, Dana, et al.
Published: (2022)

A note on strong Erdős-Hajnal for graphs with bounded VC-minimal complexity
by: Fu, Yayi
Published: (2023)

Big Ramsey combinatorics of the Cantor set and a simple proof of Blass' perfect set theorem
by: Mašulović, Dragan
Published: (2026)

Indivisibility and uniform computational strength
by: Gill, Kenneth
Published: (2023)

Decomposing graphs into stable and ordered parts
by: Buffière, Hector, et al.
Published: (2025)

Monadic Second-Order Logic of Permutations
by: Jelínek, Vít, et al.
Published: (2025)

Decidability for Sturmian words
by: Hieronymi, Philipp, et al.
Published: (2021)

Classification properties for some ternary structures
by: Miguel-Gómez, Alberto
Published: (2024)

Skelet #17 and the fifth Busy Beaver number
by: Xu, Chris
Published: (2024)

Growth of regular partitions 4: strong regularity and the pairs partition
by: Terry, C.
Published: (2024)

Foundations of iterated star maps and their use in combinatorics
by: Di Nasso, Mauro, et al.
Published: (2024)

Reductions of well-ordering principles to combinatorial theorems
by: Carlucci, Lorenzo, et al.
Published: (2024)

Undecidability of the elementary theory of Young--Fibonacci lattice
by: Evtushevsky, Vsevolod
Published: (2024)

Growth of regular partitions 3: strong regularity and the vertex partition
by: Terry, C.
Published: (2024)

Mad families of Gowers' infinite block sequences
by: Yung, Clement
Published: (2024)