Transducing Linear Decompositions of Tournaments

arXiv (Cornell University) 2026 Preprint Open access

Read full text
Authors: Colin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté
Cited by: 0

Abstract

Bojańczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-decompositions of bounded width can be produced by a CMSO transduction. We show that in the case of tournaments, a first-order transduction suffices. This implies that the logics CMSO and existential MSO are equivalent over bounded linear clique-width tournaments.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Advanced Algebra and Logic

Publication details

Journal / source
arXiv (Cornell University)
Publication date
6 January 2026
Document type
Preprint