ﻻ يوجد ملخص باللغة العربية
Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths. These results show a strong link between the properties of these graph classes considered from the point of view of structural graph theory and from the point of view of finite model theory. We take both views on classes with bounded linear rankwidth and prove structural and model theoretic properties of these classes: 1) Graphs with linear rankwidth at most $r$ are linearly mbox{$chi$-bounded}. Actually, they have bounded $c$-chromatic number, meaning that they can be colored with $f(r)$ colors, each color inducing a cograph. 2) Based on a Ramsey-like argument, we prove for every proper hereditary family $mathcal F$ of graphs (like cographs) that there is a class with bounded rankwidth that does not have the property that graphs in it can be colored by a bounded number of colors, each inducing a subgraph in~$mathcal F$. 3) For a class $mathcal C$ with bounded linear rankwidth the following conditions are equivalent: a) $mathcal C$~is~stable, b)~$mathcal C$~excludes some half-graph as a semi-induced subgraph, c) $mathcal C$ is a first-order transduction of a class with bounded pathwidth. These results open the perspective to study classes admitting low linear rankwidth covers.
We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs $C$ is monadically stable if it is impossible to define arbitrarily long linear orders in vertex-colored graphs from $C$
Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths -- a result that shows a strong link between the properties of these graph classes considered from the point of vie
Inspired by a width invariant defined on permutations by Guillemot and Marx, the twin-width invariant has been recently introduced by Bonnet, Kim, Thomasse, and Watrigant. We prove that a class of binary relational structures (that is: edge-colored p
A code ${cal C}$ is $Z_2Z_4$-additive if the set of coordinates can be partitioned into two subsets $X$ and $Y$ such that the punctured code of ${cal C}$ by deleting the coordinates outside $X$ (respectively, $Y$) is a binary linear code (respectivel
A graph $G = (V,E)$ is a double-threshold graph if there exist a vertex-weight function $w colon V to mathbb{R}$ and two real numbers $mathtt{lb}, mathtt{ub} in mathbb{R}$ such that $uv in E$ if and only if $mathtt{lb} le mathtt{w}(u) + mathtt{w}(v)