Stable graphs of bounded twin-width
Jakub Gajarský, Michał Pilipczuk, Szymon Toruńczyk
Abstract
We prove that every class of graphs that is monadically stable and has bounded twin-width can be transduced from some class with bounded sparse twin-width. This generalizes analogous results for classes of bounded linear cliquewidth [Nešetřil et al. 2021b] and of bounded cliquewidth [Nešetřil et al. 2021a]. It also implies that monadically stable classes of bounded twin-width are linearly χ-bounded.
Topics & Concepts
Bounded functionClass (philosophy)CombinatoricsMathematicsBounded deformationDiscrete mathematicsBounded operatorComputer scienceMathematical analysisArtificial intelligenceAdvanced Graph Theory ResearchFinite Group Theory ResearchGraph theory and applications