Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLinear rankwidth meets stability
314
0
0.0
(
0
)
Added by
Patrice Ossona de Mendez
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$ using a fixed first-order formula. Similarly, monadic dependence corresponds to the impossibility of defining all graphs in this way. Examples of monadically stable graph classes are nowhere dense classes, which provide a robust theory of sparsity. Examples of monadically dependent classes are classes of bounded rankwidth (or equivalently, bounded cliquewidth), which can be seen as a dense analog of classes of bounded treewidth. Thus, monadic stability and monadic dependence extend classical structural notions for graphs by viewing them in a wider, model-theoretical context. We explore this emerging theory by proving the following: - A class of graphs $C$ is a first-order transduction of a class with bounded treewidth if and only if $C$ has bounded rankwidth and a stable edge relation (i.e. graphs from $C$ exclude some half-graph as a semi-induced subgraph). - If a class of graphs $C$ is monadically dependent and not monadically stable, then $C$ has in fact an unstable edge relation. As a consequence, we show that classes with bounded rankwidth excluding some half-graph as a semi-induced subgraph are linearly $chi$-bounded. Our proofs are effective and lead to polynomial time algorithms.
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 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. The structural results we obtain are the following. 1) The number of unlabeled graphs of order $n$ with linear rank-width at most~$r$ is at most $bigl[(r/2)!,2^{binom{r}{2}}3^{r+2}bigr]^n$. 2) Graphs with linear rankwidth at most $r$ are linearly $chi$-bounded. Actually, they have bounded $c$-chromatic number, meaning that they can be colored with $f(r)$ colors, each color inducing a cograph. 3) To the contrary, based on a Ramsey-like argument, we prove for every proper hereditary family $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 $F$. From the model theoretical side we obtain the following results: 1) A direct short proof that graphs with linear rankwidth at most $r$ are first-order transductions of linear orders. This result could also be derived from Colcombets theorem on first-order transduction of linear orders and the equivalence of linear rankwidth with linear cliquewidth. 2) For a class $C$ with bounded linear rankwidth the following conditions are equivalent: a) $C$ is stable, b) $C$ excludes some half-graph as a semi-induced subgraph, c) $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.
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 partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a~proper permutation class. As a by-product, it shows that every class with bounded twin-width contains at most $2^{O(n)}$ pairwise non-isomorphic $n$-vertex graphs.
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 (respectively, a quaternary linear code). In this paper $Z_2Z_4$-additive codes are studied. Their corresponding binary images, via the Gray map, are $Z_2Z_4$-linear codes, which seem to be a very distinguished class of binary group codes. As for binary and quaternary linear codes, for these codes the fundamental parameters are found and standard forms for generator and parity check matrices are given. For this, the appropriate inner product is deduced and the concept of duality for $Z_2Z_4$-additive codes is defined. Moreover, the parameters of the dual codes are computed. Finally, some conditions for self-duality of $Z_2Z_4$-additive codes are given.
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) le mathtt{ub}$. In the literature, those graphs are studied as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs, which gives connections to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [COCOON 2018] ran in $O(n^6)$ time, where $n$ is the number of vertices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
