Zobrazeno 1 - 10
of 109
pro vyhledávání: '"de Mendez, P. Ossona"'
The $k$-th exact-distance graph, of a graph $G$ has $V(G)$ as its vertex set, and $xy$ as an edge if and only if the distance between $x$ and $y$ is (exactly) $k$ in $G$. We consider two possible extensions of this notion for signed graphs. Finding t
Externí odkaz:
http://arxiv.org/abs/2406.10780
Stability and dependence are model-theoretic notions that have recently proved highly effective in the study of structural and algorithmic properties of hereditary graph classes, and are considered key notions for generalizing to hereditary graph cla
Externí odkaz:
http://arxiv.org/abs/2405.00408
Autor:
Cortés, Pedro P., Kumar, Pankaj, Moore, Benjamin, de Mendez, Patrice Ossona, Quiroz, Daniel A.
A $k$-subcolouring of a graph $G$ is a function $f:V(G) \to \{0,\ldots,k-1\}$ such that the set of vertices coloured $i$ induce a disjoint union of cliques. The subchromatic number, $\chi_{\textrm{sub}}(G)$, is the minimum $k$ such that $G$ admits a
Externí odkaz:
http://arxiv.org/abs/2306.02195
In this paper, we survey some properties, encoding, and bijections involving combinatorial maps, double occurrence words, and chord diagrams. We particularly study quasi-trees from a purely combinatorial point of view and derive a topological represe
Externí odkaz:
http://arxiv.org/abs/2211.08259
We prove that, on bounded expansion classes, every first-order formula with modulo counting is equivalent, in a linear-time computable monadic expansion, to an existential first-order formula. As a consequence, we derive, on bounded expansion classes
Externí odkaz:
http://arxiv.org/abs/2211.03704
We continue developing the theory around the twin-width of totally ordered binary structures, initiated in the previous paper of the series. We first introduce the notion of parity and linear minors of a matrix, which consists of iteratively replacin
Externí odkaz:
http://arxiv.org/abs/2209.12023
The notions of bounded-size and quasibounded-size decompositions with bounded treedepth base classes are central to the structural theory of graph sparsity introduced by two of the authors years ago, and provide a characterization of both classes wit
Externí odkaz:
http://arxiv.org/abs/2209.11229
We study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether one can encode the other using a formula of first-order (FO) logic. In
Externí odkaz:
http://arxiv.org/abs/2208.14412
Autor:
Heydt, Ozan, Kublenz, Simeon, de Mendez, Patrice Ossona, Siebertz, Sebastian, Vigny, Alexandre
We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with bounded expansion. This generalizes a result of Czygrinow et al. for graph
Externí odkaz:
http://arxiv.org/abs/2207.02669
Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class $\mathscr{C}$ can be $\mathsf{FO}$-transduced from a class of bounded-height trees (th
Externí odkaz:
http://arxiv.org/abs/2203.16900