89 citations · 131 across the 24 of their papers we have counts for
16 papers · 1 filter
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…
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…
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…
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…
Characterisations and Examples of Graph Classes with Bounded Expansion
Jaroslav Nešetřil, Patrice Ossona de Mendez, David R. Wood
Classes with bounded expansion, which generalise classes that exclude a topological minor, have recently been introduced by Nešetřil and Ossona de Mendez. These classes are defined…