Twin-width IV: ordered graphs and matrices
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Toruńczyk
Abstract
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory.
Topics & Concepts
CombinatoricsMathematicsGraph theoryBounded functionDiscrete mathematicsClass (philosophy)Exponential functionComputer scienceArtificial intelligenceMathematical analysisAdvanced Graph Theory ResearchComplexity and Algorithms in Graphssemigroups and automata theory