89 citations · 131 across the 24 of their papers we have counts for
25 papers
Monadic dependence from reducts, and applications to twin-width of oriented graphs
Hector Buffière, Yuquan Lin, Patrice Ossona de Mendez
We study monadic dependence of binary relational structures including at least one antisymmetric relation. Our cornerstone result gives sufficient conditions for proving that a str…
Colouring negative exact-distance graphs of signed graphs
Reza Naserasr, Patrice Ossona de Mendez, Daniel A. Quiroz +2
The -th exact-distance graph, of a graph has as its vertex set, and as an edge if and only if the distance between and is (exactly) in . We consid…
Shallow vertex minors, stability, and dependence
H. Buffière, E. Kim, P. Ossona de Mendez
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, a…
Subchromatic numbers of powers of graphs with excluded minors
Pedro P. Cortés, Pankaj Kumar, Benjamin Moore +2
A -subcolouring of a graph is a function such that the set of vertices coloured induce a disjoint union of cliques. The subchromatic number…
Modulo-Counting First-Order Logic on Bounded Expansion Classes
J. Nesetril, P. Ossona de Mendez, S. Siebertz
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-or…
Decomposition horizons and a characterization of stable hereditary classes of graphs
Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez +1
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…
On first-order transductions of classes of graphs
Samuel Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez +1
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 o…
Distributed domination on sparse graph classes
Ozan Heydt, Simeon Kublenz, Patrice Ossona de Mendez +2
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 boun…
Discrepancy and Sparsity
Mario Grobler, Yiting Jiang, Patrice Ossona de Mendez +2
We study the connections between the notions of combinatorial discrepancy and graph degeneracy. In particular, we prove that the maximum discrepancy over all subgraphs of a gra…
Twin-width and permutations
Édouard Bonnet, Jaroslav Nešetřil, Patrice Ossona de Mendez +2
Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describi…
Structural properties of the first-order transduction quasiorder
Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz
Logical transductions provide a very useful tool to encode classes of structures inside other classes of structures. In this paper we study first-order (FO) transductions and the q…
Model-Checking on Ordered Structures
Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi +6
We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on…
Shrub-depth: Capturing Height of Dense Graphs
Robert Ganian, Petr Hliněný, Jaroslav Nešetřil +2
The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogousl…
Towards a Characterization of Universal Categories
J. Nesetril, P. Ossona de Mendez
In this note we characterize, within the framework of the theory of finite set, those categories of graphs that are {\em algebraic universal} in the sense that every concrete categ…
On the Generalised Colouring Numbers of Graphs that Exclude a Fixed Minor
Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz +2
The generalised colouring numbers and were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have sin…
Limits of Mappings
L. Hosseini, J. Nesetril, P. Ossona de Mendez
In this paper we consider a simple algebraic structure --- sets with a single endofunction. We shall see that from the point of view of limits, even this simplest case is both inte…
Treeable Graphings Are Local Limits of Finite Graphs
Lucas Hosseini, Patrice Ossona de Mendez
Let be a graphing, that is a Borel graph defined by measure preserving involutions. We prove that if is {\em treeable} then it arises as the local limit…
Cluster Analysis of Local Convergent Sequences of Structures
Jaroslav Nesetril, Patrice Ossona de Mendez
The cluster analysis of very large objects is an important problem, which spans several theoretical as well as applied branches of mathematics and computer science. Here we suggest…
Limits of Structures and the Example of Tree-Semilattices
Pierre Charbit, Lucas Hosseini, Patrice Ossona de Mendez
The notion of left convergent sequences of graphs introduced by Lov\' asz et al. (in relation with homomorphism densities for fixed patterns and Szemerédi's regularity lemma) got i…
First-order limits, an analytical perspective
Jaroslav Nesetril, Patrice Ossona de Mendez
In this paper we present a novel approach to graph (and structural) limits based on model theory and analysis. The role of Stone and Gelfand dualities is displayed prominently and…
Restricted frame graphs and a conjecture of Scott
Jérémie Chalopin, Louis Esperet, Zhentao Li +1
Scott proved in 1997 that for any tree , every graph with bounded clique number which does not contain any subdivision of as an induced subgraph has bounded chromatic number…
Strongly polynomial sequences as interpretations
Andrew Goodall, Jaroslav Nesetril, Patrice Ossona de Mendez
A strongly polynomial sequence of graphs is a sequence of finite graphs such that, for every graph , the number of homomorphisms from to $G_…
On First-Order Definable Colorings
Jaroslav Nesetril, Patrice Ossona De Mendez
We address the problem of characterizing -coloring problems that are first-order definable on a fixed class of relational structures. In this context, we give several characteri…
Modeling Limits in Hereditary Classes: Reduction and Application to Trees
Jaroslav Nesetril, Patrice Ossona De Mendez
Limits of graphs were initiated recently in the two extreme contexts of dense and bounded degree graphs. This led to elegant limiting structures called graphons and graphings. Thes…