Bibliography

This page has been partly generated using bibtex2html.

Abstracts: Hide/Show/Selective Show.





[Top]

Journals (with refereeing)

[A1] H. de Fraysseix, P. Ossona de Mendez, and J. Pach. Representation of planar graphs by segments. In Intuitive Geometry, volume 63 of Colloquia Mathematica Societatis János Bolyai, pages 109–117. North-Holland, 1991.
Given any bipartite planar graph G, one can assign vertical and horizontal segments to its vertices so that (a) no two of them have an interior point in common, (b) two segments have a point in common if and only if the corresponding vertices are adjacent in G.
[A2] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Combinatorics, Probability and Computing, 3:233–246, 1994.
It is proved that any plane graph may be represented by a triangle contact system, that is a collection of triangular disks which are disjoint except at contact points, each contact point being a node of exactly one triangle. Representations using contacts of T- of Y-shaped objects follow. Moreover, there is a one-to-one mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees.
[A3] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Bipolar orientations revisited. Discrete Applied Mathematics, 56:157–179, 1995. [ DOI ]
Acyclic orientations with exactly one source and one sink – the so-called bipolar orientations – arise in many graph algorithms and specially in graph drawing. The fundamental properties of these orientations are explored in terms of circuits, cocircuits and also in terms of “angles” in the planar case. Classical results get here new simple proofs; new results concern the extension of partial orientations, exhaustive enumerations, the existence of deletable and contractable edges, and continuous transitions between bipolar orientations.
[A4] H. de Fraysseix, P. Ossona de Mendez, and J. Pach. A Left-First Search Algorithm for Planar Graphs. Discrete & Computational Geometry, 13:459–468, 1995.
We give an O(|V(G)|)-time algorithm to assign vertical and horizontal segments to the vertices of any bipartite plane graph G so that (i) no two segments have an interior point in common, (ii) two segments touch each other if and only if the corresponding vertices are adjacent. As a corollary, we obtain a strengthening of the following theorem of Ringel and Petrovič. The edges of any maximal bipartite plane graph G with outer face bwb'w' can be colored by two colors such that the color classes form spanning trees of G-b and G-b', respectively. Furthermore, such a coloring can be found in linear time. Our method is based on a new linear-time algorithm for constructing bipolar orientations of 2-connected plane graphs.
[A5] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On Triangle Contact Graphs. In Combinatorics, Geometry and Probability: A Tribute to Paul Erdős, pages 165–178. Cambridge University Press, 1997.
It is proved that any plane graph may be represented by a triangle contact system, that is a collection of triangular disks which are disjoint except at contact points, each contact point being a node of exactly one triangle. Representations using contacts of T- of Y-shaped objects follow. Moreover, there is a one-to-one mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees.
[A6] H. de Fraysseix and P. Ossona de Mendez. Planarity and edge poset dimension. European Journal of Combinatorics, 17:731–740, 1997. [ DOI ]
Different areas of discrete mathematics lead to intrinsically different characterizations of planar graphs. Planarity is expressed in terms of topology, combinatorics, algebra or search trees. More recently, Schnyder's work has related planarity to partial order theory. Acyclic orientations and associated edge partial orders lead to a new characterization of planar graphs, which also describes all the possible planar embeddings. We prove here that there is a bijection between bipolar plane digraphs and 2-dimensional N-free partial orders. We give also a characterization of planarity in terms of 2-colorability of a graph and provide a short proof of a previous result on planar lattices.
[A7] H. de Fraysseix and P. Ossona de Mendez. On a Characterization of Gauss Codes. Discrete & Computational Geometry, 22(2):287–295, 1999. [ DOI ]
The traversal of a self crossing closed plane curve, with points of multiplicity at most two, defines a double occurrence sequence, the Gauss code of the curve. Using the D-switch operation, we give a new simple characterization of these sequences and deduce a simple self-contained proof of Rosenstiehl's characterization.
[A8] H. de Fraysseix and P. Ossona de Mendez. Intersection Graphs of Jordan Arcs. In Contemporary Trends in Discrete Mathematics, volume 49 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 11–28. DIMATIA-DIMACS, 1999. Štiřin 1997 Proc.
A family of Jordan arcs, such that two arcs are nowhere tangent, defines a hypergraph whose vertices are the arcs and whose edges are the intersection points. We shall say that the hypergraph has a strong intersection representation and, if each intersection point is interior to at most one arc, we shall say that the hypergraph has a strong contact representation. We first characterize those hypergraphs which have a strong contact representation and deduce some sufficient conditions for a simple planar graph to have a strong intersection representation. Then, using the Four Color Theorem, we prove that a large class of simple planar graphs have a strong intersection representation.
[A9] H. de Fraysseix and P. Ossona de Mendez. On topological aspects of orientations. Discrete Mathematics, 229(1-3):57–72, 2001. [ DOI ]
We are concerned with two classes of planar graphs: maximal planar graphs (i.e. polyhedral graphs, triangulations) and maximal bipartite planar graphs (i.e. bipartite planar graphs with quadrilateral faces). For these graphs we consider constrained orientations with a constant indegree for the internal vertex set. We recall or prove new fundamental relations between these orientations, specific tree decompositions and bipolar orientations. In particular, these relations yield linear time computation algorithms. Using these orientations, we give a characterization of 4-connected maximal planar graphs and 3-connected planar graphs, which leads to simple line time algorithms.
[A10] H. de Fraysseix and P. Ossona de Mendez. Connectivity of planar graphs. Journal of Graph Algorithms and Applications, 5(5):93–105, 2001.
We give here three simple linear time algorithms on planar graphs: a 4-connexity test for maximal planar graphs, an algorithm enumerating the triangles and a 3-connexity test. Although all these problems got already linear-time solutions, the presented algorithms are both simple and efficient. They are based on some new theoretical results.
[A11] P. Ossona de Mendez. Realization of posets. Journal of Graph Algorithms and Applications, 6(1):149–153, 2002.
We prove a very general representation theorem for posets and, as a corollary, deduce that any abstract simplicial complex S has a geometric realization in the Euclidean space of dimension P(S)-1, where P(S) is the Dushnik-Miller dimension of the face order of S.
[A12] J. Nešetřil and P. Ossona de Mendez. Colorings and homomorphisms of minor closed classes. In B. Aronov, S. Basu, J. Pach, and M. Sharir, editors, The Goodman-Pollack Festschrift, volume 25 of Algorithms and Combinatorics, pages 651–664. Discrete & Computational Geometry, 2003.
We relate acyclic (and star) chromatic number of a graph to the chromatic number of its minors and as a consequence we show that the set of all triangle free planar graphs is homomorphism bounded by a triangle free graph. It also improves the best known bound for the star chromatic number of planar graphs from 80 to 30. Our method generalizes to all minor closed classes and puts Hadwiger conjecture in yet another context.
[A13] H. de Fraysseix and P. Ossona de Mendez. On cotree-critical and DFS cotree-critical graphs. Journal of Graph Algorithms and Applications, 7(4):411–427, 2003. [ .pdf ]
We give a characterization of DFS cotree-critical graphs which is central to the linear time Kuratowski finding algorithm implemented in PIGALE (Public Implementation of a Graph Algorithm Library and Editor) by the authors, and deduce an algorithm for finding a Kuratowski subdivision in a DFS cotree-critical graph.
[A14] P. Ossona de Mendez and P. Rosenstiehl. Transitivity and connectivity of permutations. Combinatorica, 24(3):487–502, 2004. [ DOI ]
It was known for years, in quantic physics especially, that the connected permutations (also called indecomposable permutations) of [0;n], i.e. those such that for any i<n there exists j>i with p(j)<i, are as many as the pointed hypermaps of size n, i.e. the transitive pairs (p,q) of permutations of a set of cardinality n with a distinguished element. The paper establishes a natural bijection between the two families. An encoding of maps follows.
[A15] P. Ossona de Mendez. Realization of posets. In Graph Algorithms and Applications 3, pages 149–153. World Scientific, 2004.
[A16] H. de Fraysseix and P. Ossona de Mendez. Connectivity of planar graphs. In Graphs Algorithms and Applications 2. World Scientific, 2004.
[A17] P. Ossona de Mendez and P. Rosenstiehl. Homomorphism and dimension. Combinatorics, Probability and Computing, 14(5-6):861–872, 2005. [ DOI ]
The dimension of a graph, that is the dimension of its incidence poset, became a major bridge between posets and graphs. Although allowing a nice characterization of planarity, this dimension badly behaves with respect to homomorphisms. We introduce the universal dimension of a graph G as the maximum dimension of a graph having a homomorphism to G. The universal dimension, which is clearly homomorphism monotone, is related to the existence of some balanced bicoloration of the vertices with respect to some realizer. Non trivial new results related to the original graph dimension are subsequently deduced from our study of universal dimension, including chromatic and extremal properties.
[A18] J. Nešetřil and P. Ossona de Mendez. Cuts and bounds. Discrete Mathematics, Structural Combinatorics - Combinatorial and Computational Aspects of Optimization, Topology and Algebra, 302(1-3):211–224, 2005. [ DOI ]
We consider the colouring (or homomorphism) order C induced by all finite graphs and the existence of a homomorphism between them. This ordering may be seen as a lattice which is however far from being complete. In this paper we study bounds, suprema and maximal elements in C of some frequently studied classes of graphs (such as bounded degree, degenerated and classes determined by a finite set of forbidden subgraphs). We relate these extrema to cuts of subclasses K of C (cuts are finite sets which are comparable to every element of the class K). We determine all cuts for classes of degenerated graphs. For classes of bounded degree graphs this seems to be a very difficult problem which is also mirrored by the fact that these classes fail to have a supremum. We note a striking difference between undirected and oriented graphs. This is based on the recent work of C. Tardif and J. Nešetřil. Also minor closed classes are considered and we survey recent results obtained by authors. A bit surprisingly this order setting captures Hadwiger conjecture and suggests some new problems.
[A19] P. Ossona de Mendez and P. Rosenstiehl. Encoding pointed maps by double occurrence words. In University of Piraeus, editor, Volume of essays in honour of Professor Antonios C. Panayotopoulos, pages 701–712. Eptalofos, 2006.
We show that pointed maps with m edges are in bijection with standard double occurrence words with (m+1) symbols.
[A20] J. Nešetřil and P. Ossona de Mendez. Tree depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics, 27(6):1022–1041, 2006. [ DOI ]
We define the notions tree depth and upper chromatic number of a graph and show their relevance to local - global problems for graphs partitions. Particularly we show that the upper chromatic number coincides with the maximal function which can be locally demanded in a bounded coloring of any proper minor closed class of graphs. The rich interplay of these notions is applied to a solution of bounds of proper minor closed classes satisfying local conditions. Particularly, we prove the following result: For every graph M and a finite set F of connected graphs there exists a (universal) graph U = U(M, F) ∈Forb(F) such that any graph GForb(F) which does not have M as a minor satisfies GU (i.e. is homomorphic to U). This solves the main open problem of restricted dualities for minor closed classes and as an application it yields the bounded chromatic number of exact odd powers of any graph in an arbitrary proper minor closed class. We also generalize the decomposition theorem of DeVos et al.
[A21] J. Nešetřil and P. Ossona de Mendez. Folding. Journal of Combinatorial Theory, Series B, 96(5):730–739, 2006. [ DOI ]
We define folding of a directed graph as a coloring (or a homomorphism) which is injective on all the down sets of a given depth. While in general foldings are as complicated as homomorphisms for some some classes they present an useful tool to study colorings and homomorphisms. Our main result yields for any proper minor closed class C a folding (of any prescribed depth) using a fixed number of colors. This in turn yields (for any C) the existence of a Kk-free graph which bounds all Kk-free graphs belonging to C. This has been conjectured and solved for k=3. Particularly, we prove (without using 4CT) the existence of a graph H with chromatic number at most 5 and clique number at most 4, such that any planar graph G is homomorphic to H. This is sandwiched between 4CT and 5CT for planar graphs and the general case has bearing to Hadwiger Conjecture.
[A22] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Depth-first search and planarity. International Journal of Foundations of Computer Science, 17(5):1017–1029, 2006. Special Issue on Graph Drawing. [ DOI ]
We present a simplified version of the DFS-based Left-Right planarity testing and embedding algorithm implemented in Pigale which has been considered as the fastest implemented one [J.M. Boyer, P.F. Cortese, M. Patrignani, and G. Di Battista. Stop minding your P's and Q's: implementing fast and simple DFS-based planarity and embedding algorithm. In Graph Drawing, volume 2912 of Lecture Notes in Computer Science, pages 25–36. Springer, 2004.]. We give here a simple full justification of the algorithm, based on a preliminary extended study of topological properties of DFS trees.
[A23] H. de Fraysseix and P. Ossona de Mendez. Regular embeddings of multigraphs. In M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas, and P. Valtr, editors, Topics in Discrete Mathematics, volume 26 of Algorithms and Combinatorics, pages 553–563. Springer-Verlag, 2006. Dedicated to Jarik Nešetřil on the occasion of his 60th birthday.
We prove that the vertex set of any twin-free multigraph G has an embedding into some point set P of some Euclidean space Rk, such that the automorphism group of G is isomorphic to the isometry group of Rk globally preserving P.
[A24] H. de Fraysseix and P. Ossona de Mendez. On representations by contact and intersection of segments. Algorithmica, 47(4):453–463, 2007. [ DOI ]
A necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a contact family of segments and points. We deduce that any 4-connected 3-colorable plane graph is the contact graph of a family of segments and that any 4-colored planar graph without an induced C4 using 4 colors is the intersection graph of a family of straight line segments.
[A25] H. de Fraysseix and P. Ossona de Mendez. Barycentric systems and stretchability. Discrete Applied Mathematics, 155(9):1079–1095, 2007. [ DOI ]
Using a general resolution of barycentric systems we give a generalization of Tutte's theorem on convex drawing of planar graphs. We deduce a characterization of the edge coverings into pairwise non-crossing paths which are stretchable: such a system is stretchable if and only if each subsystem of at least two paths has at least 3 free vertices (vertices of the outer face of the induced subgraph which are internal to none of the paths of the subsystem). We also deduce that a contact system of pseudo-segments is stretchable if and only if it is extendible.
[A26] J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion III. Restricted graph homomorphism dualities. European Journal of Combinatorics, 29(4):1012–1024, 2008. [ DOI ]
We study restricted homomorphism dualities in the context of classes with bounded expansion. This presents a generalization of restricted dualities obtained earlier for bounded degree graphs and also for proper minor closed classes. This is related to distance coloring of graphs and to the “approximative version” of Hadwiger conjecture.
[A27] J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion II. Algorithmic aspects. European Journal of Combinatorics, 29(3):777–791, 2008. [ DOI ]
Classes of graphs with bounded expansion are a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇r(G). These classes are also characterized by the existence of several partition results such as the existence of low tree-width and low tree-depth colorings. These results lead to several new linear time algorithms, such as an algorithm for counting all the isomorphs of a fixed graph in an input graph or an algorithm for checking whether there exists a subset of vertices of a priori bounded size such that the subgraph induced by this subset satisfies some arbirtrary but fixed first order sentence. We also show that for fixed p, computing the distances between two vertices up to distance p may be performed in constant time per query after a linear time preprocessing. We also show, extending several earlier results, that a class of graphs has sublinear separators if it has sub-exponential expansion. This result result is best possible in general.
[A28] J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion I. Decompositions. European Journal of Combinatorics, 29(3):760–776, 2008. [ DOI ]
We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇r(G). For these classes we prove the existence of several partition results such as the existence of low tree-width and low tree-depth colorings. This generalizes and simplifies several earlier results (obtained for minor closed classes).
[A29] J. Nešetřil and P. Ossona de Mendez. Fraternal augmentations, arrangeability and linearly bounded Ramsey numbers. European Journal of Combinatorics, 30(7):1696–1703, 2009. [ DOI ]
We characterize arrangeability and admissibility in terms of ∇1(G) (Burr – Erdős conjecture relates to ∇0(G)). This implies the linearity of the Ramsey number and bounded game chromatic number for some new classes of graphs.
[A30] J. Nešetřil and P. Ossona de Mendez. First order properties on nowhere dense structures. The Journal of Symbolic Logic, 75(3):868–887, 2010. [ DOI ]
A set A of vertices of a graph G is called d-scattered in G if no two d-neighborhoods of (distinct) vertices of A intersect. In other words, A is d-scattered if no two distinct vertices of A have distance at most 2d. This notion was isolated in the context of finite model theory by Ajtai and Gurevich and recently it played a prominent role in the study of homomorphism preservation theorems for special classes of structures (such as minor closed classes). This in turn led to the notions of wide, almost wide and quasi-wide classes of graphs. It has been proved previously that minor closed classes and classes of graphs with locally forbidden minors are examples of such classes and thus (relativized) homomorphism preservation theorem holds for them. In this paper we show that (more general) classes with bounded expansion and (newly defined) classes with bounded local expansion and even (very general) nowhere dense classes are quasi wide. This not only strictly generalizes the previous results but it also provides new proofs and algorithms for some of the old results. It appears that bounded expansion and nowhere dense classes are perhaps a proper setting for investigation of wide-type classes as in several instances we obtain a structural characterization. This also puts classes of bounded expansion in the new context. Our motivation stems from finite dualities. As a corollary we obtain that any homomorphism closed first order definable property restricted to a bounded expansion class is a restricted duality.
[A31] J. Nešetřil and P. Ossona de Mendez. Extremal problems for sparse graphs. In I. Bárány and J. Solymosi, editors, An irregular mind (Szemerédi is 70), volume 21 of Bolyai Society Mathematical Studies, pages 447–490. Springer, 2010.
We survey some of the recent results related to the study of sparse graphs using the nowhere dense - somewhere dense dichotomy. Particularly we extend known results related to property testing, sublinear expanders, Ramsey numbers and FO model checking. All this is done under the same umbrella of nowhere dense and bounded expansion classes in many of their incarnations. We concentrate on extremal (mostly graph theory) results leaving algorithmic and structural aspects to other occasions.
[A32] J. Nešetřil and P. Ossona de Mendez. How many F's are there in G? European Journal of Combinatorics, 32(7):1126–1141, 2011. [ DOI ]
We prove that the asymptotic logarithmic density of copies of a graph F in the graphs of a nowhere dense class C is integral and we determine the range of its possible values. This leads to a generalization of the Trichotomy theorem [33] and to a notion of degree of freedom of a graph F in a class C. This provides yet another formulation of the somewhere dense – nowhere dense classification. We obtain a structural result about the asymptotic shape of graphs with given degree of freedom.
[A33] J. Nešetřil and P. Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600–617, 2011. [ DOI ]
In this paper we define and analyze the nowhere dense classes of graphs. This notion is a common generalization of proper minor closed classes, classes of graphs with bounded degree, locally planar graphs, classes with bounded expansion, to name just a few classes which are studied extensively in combinatorial and computer science contexts. In this paper we show that this concept leads to a classification of general classes of graphs and to the dichotomy between nowhere dense and somewhere dense classes. This classification is surprisingly stable as it can be expressed in terms of the most commonly used basic combinatorial parameters, such as the independence number α, the clique number ω, and the chromatic number χ. The remarkable stability of this notion and its robustness has a number of applications to mathematical logic, complexity of algorithms, and combinatorics. We also express the nowhere dense versus somewhere dense dichotomy in terms of edge densities as a trichotomy theorem.
[A34] F. Fiorenzi, P. Ochem, P. Ossona de Mendez, and X. Zhu. Thue choosability of trees. Discrete Applied Mathematics, 159:2045–2049, 2011. [ DOI ]
A vertex colouring of a graph G is nonrepetitive if for any path P = (v1, v2,...., v2r) in G, the first half is coloured differently from the second half. The Thue choice number of G is the least integer l such that for every l-list assignment L of G, there exists a nonrepetitive L-colouring of G. We prove that for any positive integer l, there is a tree T with πch(T) > l. On the other hand, it is proved that if G' is a graph of maximum degree Δ, and G is obtained from G' by attaching to each vertex v of G' a graph of tree-depth at most d rooted at v, then πch(G)≤c(, d) for some constant c(Δ, d) depending only on Δ and d.
[A35] J. Nešetřil, P. Ossona de Mendez, and D.R. Wood. Characterizations and examples of graph classes with bounded expansion. European Journal of Combinatorics, 33(3):350–373, 2012. [ DOI ]
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 by the fact that the maximum average degree of a shallow minor of a graph in the class is bounded by a function of the depth of the shallow minor. Several linear-time algorithms are known for bounded expansion classes (such as subgraph isomorphism testing), and they allow restricted homomorphism dualities, amongst other desirable properties. In this paper we establish two new characterisations of bounded expansion classes, one in terms of so-called topological parameters, the other in terms of controlling dense parts. The latter characterisation is then used to show that the notion of bounded expansion is compatible with Erdös-Rényi model of random graphs with constant average degree. In particular, we prove that for every fixed d>0, there exists a class with bounded expansion, such that a random graph of order n and edge probability d/n asymptotically almost surely belongs to the class. We then present several new examples of classes with bounded expansion that do not exclude some topological minor, and appear naturally in the context of graph drawing or graph colouring. In particular, we prove that the following classes have bounded expansion: graphs that can be drawn in the plane with a bounded number of crossings per edge, graphs with bounded stack number, graphs with bounded queue number, and graphs with bounded non-repetitive chromatic number. We also prove that graphs with `linear' crossing number are contained in a topologically-closed class, while graphs with bounded crossing number are contained in a minor-closed class.
[A36] J. Nešetřil and P. Ossona de Mendez. A model theory approach to structural limits. Commentationes Mathematicæ Universitatis Carolinæ, 53(4):581–603, 2012.
The goal of this paper is to unify two lines in a particular area of graph limits. First, we generalize and provide unified treatment of various graph limit concepts by means of a combination of model theory and analysis. Then, as an example, we generalize limits of bounded degree graphs from subgraph testing to finite model testing.

[A37] M. Montassier, P. Ossona de Mendez, A. Raspaud, and X. Zhu. Decomposing a graph into forests. Journal of Combinatorial Theory, Series B, 102(1):38–52, 2012. [ DOI ]
In this paper, we propose a conjecture which says that every graph G with γf(G) ≤k+ (d)/(k+d+1) decomposes into k+1 forests, and one of the forests has maximum degree at most d. We prove two special cases of this conjecture: If G is a graph with fractional arboricity at most (43, then G decomposes into a forest and a matching. If G is a graph with fractional arboricity at most (32, then G decomposes into a forest and a linear forest. In particular, every planar graph of girth at least 8 decomposes into a forest and a matching, and every planar graph of girth at least 6 decomposes into a forest and a linear forest. This improves earlier results concerning decomposition of planar graphs. We give examples to show that there are planar graphs of girth 7 which does not decompose into a forest and a matching, and there are planar graphs of girth 5 which does not decompose into a forest and a linear forest. We also show that the bound in the conjecture above is sharp, i.e., for any ε> 0, there is a graph G with γf(G) < k+ (d)/(k+d+1) +ε, and yet G cannot be decomposed into k+1 forests, with one of them having maximum degree at most d.)/())/()
[A38] H. de Fraysseix and P. Ossona de Mendez. Planarity and Trémaux trees. European Journal of Combinatorics, 33(3):279–293, 2012. [ DOI ]
We present a characterization of planarity based on Trémaux trees (i.e. DFS trees), from which we deduce a simple and efficient planarity test algorithm. We finally recall a theorem on “cotree critical non-planar graphs" which very much simplify the search of a Kuratowski subdivision in a non-planar graph.
[A39] J. Nešetřil and P. Ossona de Mendez. A note on Fiedler value of classes with sublinear separators. Linear Algebra and its Applications, 439:2216–2221, 2013. [ DOI | http ]
The n-th Fiedler value of a class of graphs C is the maximum second eigenvalue λ2(G) of a graph G∈C with n vertices. In this note we relate this value to shallow minors and, as a corollary, we determine the right order of the n-th Fiedler value for some minor closed classes of graphs, including the class of planar graphs.

[A40] J. Nešetřil, P. Ossona de Mendez, and X. Zhu. Coloring edges with many colors in cycles. Journal of Combinatorial Theory, Series B, 109:102–119, 2014. [ DOI ]
The arboricity of a graph G is the minimum number of colors needed to color the edges of G so that every cycle gets at least two colors. Given a positive integer p, we define the generalized p-arboricity p(G) of a graph G as the minimum number of colors needed to color the edges of a multigraph G in such a way that every cycle C gets at least min(|C|,p+1) colors. In the particular case where G has girth at least p+1, p(G) is the minimum size of a partition of the edge set of G such that the union of any p parts induce a forest. If we require further that the edge colouring be proper, i.e., adjacent edges receive distinct colours, then the minimum number of colours needed is the generalized p-acyclic edge chromatic number of G. In this paper, we relate the generalized p-acyclic edge chromatic numbers and the generalized p-arboricities of a graph G to the density of the multigraphs having a shallow subdivision as a subgraph of G.
[A41] J. Nešetřil and P. Ossona de Mendez. On low tree-depth decompositions. Graphs and Combinatorics, 31(6):1941–1963, 2015. [ DOI ]
The theory of sparse structures usually uses tree like structures as building blocks. In the context of sparse/dense dichotomy this role is played by graphs with bounded tree-depth. In this paper we survey results related to this concept and particularly explain how these graphs are used to decompose and construct more complex graphs and structures. In more technical terms we survey some of the properties and applications of low tree-depth decomposition of graphs.
[A42] J. Nešetřil and P. Ossona de Mendez. A note on circular chromatic number of graphs with large girth and similar problems. Journal of Graph Theory, 80(4):268–276, 2015. [ DOI ]
In this short note, we extend the result of Galluccio, Goddyn, and Hell, which states that graphs of large girth excluding a minor are nearly bipartite. We also prove a similar result for the oriented chromatic number, from which follows in particular that graphs of large girth excluding a minor have oriented chromatic number at most 5, and for the pth chromatic number χp, from which follows in particular that graphs G of large girth excluding a minor have χp(G)≤p+2.
[A43] J. Nešetřil and P. Ossona de Mendez. On first-order definable colorings. In J. Nešetřil and M. Pellegrini, editors, Geometry, Structure and Randomness in Combinatorics, volume 18 of Publications of the Scuola Normale Superiore, CRM Series, pages 99–122. Edizioni della Normale, 2015.
We address the problem of characterizing H-coloring problems that are first-order definable on a fixed class of relational structures. In this context, we give several characterizations of a homomorphism dualities arising in a class of structure.

[A44] P. Ossona de Mendez, S. Oum, and D.R. Wood. Defective colouring of graphs excluding a subgraph or minor. 2016. submitted.
Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3-coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015) proved that graphs with no Kt+1-minor can be t-coloured so that each colour class induces asubgraph of bounded maximum degree. We prove a common generalisation of these theorems with a weaker assumption about excluded subgraphs. This result leads to new defective colouring results for several graph classes, including graphs with linear crossing number, graphs with given thickness, graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs excluding a complete bipartite graph as a topological minor.
[A45] J. Nešetřil and P. Ossona de Mendez. Structural sparsity. Uspekhi Matematicheskikh Nauk, 71(1):85–116, 2016. (Russian Math. Surveys 71:1 79-107). [ DOI ]
We discuss the notion of structural sparsity and how it relates to the nowhere dense/somewhere dense dichotomy introduced by the authors for classes of graphs. This will be the occasion of surveying the numerous facets of this dichotomy, as well as its connections to several concepts like stability, independence, VC-dimension, regularity partitions, entropy, class speed, low tree-depth decomposition, quasi-wideness, neighborhood covering, subgraph statistics, etc. as well as algorithmic complexity issues like fixed parameter tractability of first-order model checking.
[A46] J. Nešetřil and P. Ossona de Mendez. First-order limits, an analytical perspective. European Journal of Combinatorics, 52 Part B:368–388, 2016. [ DOI ]
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 leads to a general theory, which we believe is naturally emerging. This approach covers all the particular examples of structural convergence and it put the whole in new context. As an application, it leads to new intermediate examples of structural convergence and to a “grand conjecture” dealing with sparse graphs. We survey the recent developments.
[A47] J. Nešetřil and P. Ossona de Mendez. Existence of modeling limits for sequences of sparse structures. 2016. submitted.
Let G be a graphing, that is a Borel graph defined by d measure preserving involutions. We prove that if G is treeable then it arises as the local limit of some sequence (Gn)n&isin;ℕ of graphs with maximum degree at most d. This extends a result by Elek [G. Elek, Note on limits of finite graphs, Combinatorica 27 (2007)] (for G a treeing) and consequently extends the domain of the graphings for which Aldous–Lyons conjecture is known to be true.
[A48] J. Nešetřil and P. Ossona de Mendez. A distributed low tree-depth decomposition algorithm for bounded expansion classes. Distributed Computing, 29(1):39–49, 2016. [ DOI ]
We study the distributed low tree-depth decomposition problem for graphs restricted to a bounded expansion class. Low tree-depth decomposition have been introduced in 2006 and have found quite a few applications. For example it yields a linear-time model checking algorithm for graphs in a bounded expansion class. Recall that bounded expansion classes cover classes of graphs of bounded degree, of planar graphs, of graphs of bounded genus, of graphs of bounded treewidth, of graphs that exclude a fixed minor, and many other graphs. There is a sequential algorithm to compute low tree-depth decomposition (with bounded number of colors) in linear time. In this paper, we give the first efficient distributed algorithm for this problem. As it is usual for a symmetry breaking problem, we consider a synchronous model, and as we are interested in a deterministic algorithm, we use the usual assumption that each vertex has a distinct identity number. We consider the distributed message-passing CONGESTBC model, in which messages have logarithmic length and only local broadcast are allowed. In this model, we present a logarithmic time distributed algorithm for computing a low tree-depth decomposition of graphs in a fixed bounded expansion class. In the sequential centralized case low tree-depth decomposition linear time algorithm are used as a core procedure in several non-trivial linear time algorithms. We believe that, similarly, low tree-depth decomposition could be at the heart of several non-trivial logarithmic time algorithms.
[A49] J. Nešetřil and P. Ossona de Mendez. Towards a characterization of universal categories. Journal of Pure and Applied Algebra, 2016. [ DOI ]
Let G be a graphing, that is a Borel graph defined by d measure preserving involutions. We prove that if G is treeable then it arises as the local limit of some sequence (Gn)n&isin;ℕ of graphs with maximum degree at most d. This extends a result by Elek [G. Elek, Note on limits of finite graphs, Combinatorica 27 (2007)] (for G a treeing) and consequently extends the domain of the graphings for which Aldous–Lyons conjecture is known to be true.
[A50] J. Chalopin, L. Esperet, Z. Li, and P. Ossona de Mendez. Restricted frame graphs and a conjecture of Scott. Electronic Journal of Combinatorics, 23(1):#P1.30, 2016.
Scott proved in 1997 that for any tree T, every graph with bounded clique number which does not contain any subdivision of T as an induced subgraph has bounded chromatic number. Scott also conjectured that the same should hold if T is replaced by any graph H. Pawlik et al. recently constructed a family of triangle-free intersection graphs of segments in the plane with unbounded chromatic number (thereby disproving an old conjecture of Erdős). This shows that Scott's conjecture is false whenever H is obtained from a non-planar graph by subdividing every edge at least once. It remains interesting to decide which graphs H satisfy Scott's conjecture and which do not. In this paper, we study the construction of Pawlik et al. in more details to extract more counterexamples to Scott's conjecture. For example, we show that Scott's conjecture is false for any graph obtained from K4 by subdividing every edge at least once. We also prove that if G is a 2-connected multigraph with no vertex intersecting every cycle of G, then any graph obtained from G by subdividing every edge at least twice is a counterexample to Scott's conjecture.
[A51] A.J. Goodall, J. Nešetřil, and P. Ossona de Mendez. Strongly polynomial sequences as interpretations. Journal of Applied Logic, May 2016. in press; available online. [ DOI ]
A strongly polynomial sequence of graphs (Gn) is a sequence (Gn)n&isin;ℕ of finite graphs such that, for every graph F, the number of homomorphisms from F to Gn is a fixed polynomial function of n (depending on F). For example, (Kn) is strongly polynomial since the number of homomorphisms from F to Kn is the chromatic polynomial of F evaluated at n. In earlier work of de la Harpe and Jaeger, and more recently of Averbouch, Garijo, Godlin, Goodall, Makowsky, Nešetřil, Tittmann, Zilber and others, various examples of strongly polynomial sequences and constructions for families of such sequences have been found, leading to analogues of the chromatic polynomial for fractional colourings and acyclic colourings, to choose two interesting examples. %Many graph polynomials, such as the Tutte polynomial and independence polynomial, are determined by strongly polynomial sequences of graphs. We give a new model-theoretic method of constructing strongly polynomial sequences of graphs that uses interpretation schemes of graphs in more general relational structures. This surprisingly easy yet general method encompasses all previous constructions and produces many more. We conjecture that, under mild assumptions, all strongly polynomial sequences of graphs can be produced by the general method of quantifier-free interpretation of graphs in certain basic relational structures (essentially disjoint unions of transitive tournaments with added unary relations). We verify this conjecture for strongly polynomial sequences of graphs with uniformly bounded degree.
[A52] J. Nešetřil and P. Ossona de Mendez. Modeling limits in hereditary classes: Reduction and application to trees. Electronic Journal of Combinatorics, 23(2):#P2.52, December 2016.
The study of limits of graphs led to elegant limiting structures for sparse and dense graphs. This has been unified and generalized by authors in a more setting combining analytic tools and model theory to FO-limits (and X-limits) and to the notion of modeling. The existence of modeling limits was established for sequences in a bounded degree class and, in addition, to the case of classes of trees with bounded height and of graphs with bounded tree depth. The natural obstacle for the existence of modeling limit for a monotone class of graphs is the nowhere dense property and it has been conjectured that this is a sufficient condition. Extending earlier results here we derive several general results which present a realistic approach to this conjecture. As an example we then prove that the class of all finite trees admits modeling limits.
[A53] J. Nešetřil and P. Ossona de Mendez. Limits of mappings. European Journal of Combinatorics, 66:145–159, 2017.
[A54] J. Nešetřil and P. Ossona de Mendez. Cluster analysis of local convergent sequences of structures. Random Structures & Algorithms, 2017. available online. [ DOI ]
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 a novel approach: under assumption of local convergence of a sequence of finite structures we derive an asymptotic clustering. This is achieved by a blend of analytic and geometric techniques, and particularly by a new interpretation of the authors' representation theorem for limits of local convergent sequences, which serves as a guidance for the whole process. Our study may be seen as an effort to describe connectivity structure at the limit (without having a defined explicit limit structure) and to pull this connectivity structure back to the finite structures in the sequence in a continuous way.
[A55] J. Nešetřil and P. Ossona de Mendez. A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth). Memoirs of the American Mathematical Society, 2017. accepted.
In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on model theory and analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as “tractable cases” of a general theory. As an outcome of our theory, we provide extensions of known results and identify some new cases exhibiting specific properties suggesting that their study could be more accessible than the full general case. The second part of the paper is devoted to the study of such a case, namely limits of graphs (and structures) with bounded diameter connected components.

We prove that in this case the convergence can be “almost” studied component-wise. Eventually, we consider the specific case of limits of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of modeling we introduce here. It is also the first “intermediate class” with explicitly defined limit structures.

[A56] J. van den Heuvel, P. Ossona de Mendez, D. Quiroz, R. Rabinovich, and S. Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. European Journal of Combinatorics, 66:129–144, 2017.
[A57] P. Charbit, L. Hosseini, and P. Ossona de Mendez. Limits of structures and the example of tree-semilattices. Discrete Mathematics, 340:2589–2603, 2017. [ DOI ]
The notion of left convergent sequences of graphs introduced by Lovász et al. (in relation with homomorphism densities for fixed patterns and Szemerédi's regularity lemma) got increasingly studied over the past 10 years. Recently, Nešetřil and Ossona de Mendez introduced a general framework for convergence of sequences of structures. In particular, the authors introduced the notion of QF-convergence, which is a natural generalization of left-convergence. In this paper, we initiate study of QF-convergence for structures with functional symbols by focusing on the particular case of tree semi-lattices. We fully characterize the limit objects and give an application to the study of left convergence of m-partite cographs, a generalization of cographs.

[Top]

Conference Proceedings (with refereeing)

[P1] H. de Fraysseix and P. Ossona de Mendez. Regular Orientations, Arboricity and Augmentation. In DIMACS International Workshop, Graph Drawing 94, volume 894 of Lecture notes in Computer Science, pages 111–118, 1995. [ DOI ]
Regular orientations, that is orientations such that almost all the vertices have the same indegree, relates many combinatorial and topological properties, such as arboricity, page number, and planarity. These orientations are a basic tool in solving combinatorial problems that preserve topological properties. Planar augmentations are a simple example of such problems.
[P2] H. de Fraysseix and P. Ossona de Mendez. A short proof of a Gauss problem. In G. DiBattista, editor, Graph Drawing Proceedings, volume 1353 of Lecture Notes in Computer Science, pages 230–235. Springer, 1997. [ DOI ]
The traversal of a self crossing closed plane curve, with points of multiplicity at most two, defines a double occurrence sequence. C.F. Gauss conjectured that such sequences could be characterized by their interlacement properties. This conjecture was proved by P. Rosenstiehl in 1976. We shall give here a simple self-contained proof of his characterization. This new proof relies on the D-switch operation.
[P3] P. Ossona de Mendez. The Reduced Genus of a Multigraph. In STACS 99, volume 1563 of Lecture notes in Computer Science, pages 16–31. Springer, 1999.
We define here the reduced genus of a multigraph as the minimum genus of a hypergraph having the same adjacencies with the same multiplicities. Through a study of embedded hypergraphs, we obtain new bounds on the coloring number, clique number and point arboricity of simple graphs of a given reduced genus. We present some new related problems on graph coloring and graph representation.
[P4] P. Ossona de Mendez. Geometric Realization of Simplicial Complexes. In J. Kratochvil, editor, Graph Drawing, volume 1731 of Lecture Notes in Computer Science, pages 323–332. Springer, 1999.
We show that an abstract simplicial complex S may be realized on (d-1)-dimensional space, where d=P(S) is the order dimension (Dushnik-Miller dimension) of the face poset of S.
[P5] P. Ossona de Mendez and P. Rosenstiehl. What search for graph drawing. In IIIS, editor, World Multiconference on Systemics, Cybernetics and Informatics, volume XI, pages 125–130, 2000.
Drawing combinatorial structures is a new challenge aimed to a better control of data in industry and in business as well. Speaking of graph we often understand map since a rotation system of edges around the vertices is specified by the context or by choice of the data structures. Search is the crucial step in the process of drawing. Depth-First Search has generated in the past well known algorithms for planarity testing, map transformation, graph drawing. Breadth-First Search on the counterpart was rather neglected and appears to be the right tool for coding and drawing maps. A bijection is proposed here, between the pointed maps with m edges and the connected involutions on {0,1,...,2m+1}.
[P6] P. Ossona de Mendez. Combinatorial hypermaps vs topic maps. In XML Europe 2001, 2001. [ .html ]
Topic Maps have been introduced to interchangeably represent information about the structure of information resources used to define topics, and the relationships between topics. Graphs and hypergraphs have been introduced in discrete mathematics for a similar reason. Industrial needs related to Topic Maps not only rely on their representations in a data structure, but also deals with new complex information extraction requests, like Navigation, Structure Analysis, Minimal Cut search, etc. The adapted paradigm seems to be the one of a combinatorial hypermap, which has been introduced some decades ago. This paper presents this combinatorial object, associated data structures and algorithmic considerations about it. Topological graph theory is shown to be the right mathematical and algorithmic tool to handle Topic Maps efficiently.
[P7] H. de Fraysseix and P. Ossona de Mendez. An algorithm to find a Kuratowski subdivision in DFS cotree critical graphs. In Edy Try Baskoro, editor, Proceedings of the Twelfth Australasian Workshop on Combinatorial Algorithms (AWOCA 2000), pages 98–105, Indonesia, 2001. Institut Teknologi Bandung.
We present a simple linear time algorithm finding a Kuratowski subdivision in a DFS cotree critical graphs, based on recent theoretical results. For sake of clarity, we shall outline the proofs of the Theorem we make use of. This algorithm is the last part of the two step linear time Kuratowski finding algorithm implemented in PIGALE (“Public Implementation of a Graph Algorithm Library and Editor”, freely available at http://pigale.sourceforge.org).
[P8] H. de Fraysseix and P. Ossona de Mendez. A characterization of DFS cotree critical graphs. In Graph Drawing, volume 2265 of Lecture notes in Computer Science, pages 84–95, 2002.
We give a characterization of DFS-cotree critical graphs which is central to the linear time Kuratowski finding algorithm implemented in PIGALE
[P9] P. Auillans, P. Ossona de Mendez, P. Rosenstiehl, and B. Vatant. A formal model for topic maps. In Ian Horrocks and James Hendler, editors, The Seamntic Web - ISWC 2002, volume 2342 of Lecture notes in Computer Science, pages 69–83, 2002. [ http ]
Topic Maps have been developed in order to represent the structures of relationships between subjects, independently of resources documenting them, and to allow standard representation and interoperability of such structures. The ISO 13250 XTM specification have provided a robust syntactic XML representation allowing processing and interchange of topic maps. But topic maps have so far suffered from a lack of formal description, or conceptual model. We propose here such a model, based on the mathematical notions of hypergraph and connexity. This model addresses the critical issue of topic map organization in semantic layers, and provides ways to check semantic consistency of topic maps. Moreover, it seems generic enough to be used as a foundation for other semantic standards, like RDF.
[P10] P. Ossona de Mendez, M.V. Santos, and I. Woungang. Pliant: more than a programming language, a flexible e-learning tool. In World Conference on Educational Multimedia, Hypermedia and Telecommunications (EDMEDIA), volume 2004 issue 1, pages 505–510, 2004. [ http ]
The increasing importance of e-learning has been a boosting element for the emergence of Internet based education services. As we move into the information age, tremendous efforts are continuously made in the development of new Web Technologies for educational services, while meeting the human resource and economical expectations. This paper reports on the capabilities of Pliant as a flexible software tool for enhancing the development of e-Learning management systems, while meeting educational and software-oriented expectations. This paper reports on the capabilities of Pliant as a new software tool and Web-based technology dedicated for e-learning and distance learning purposes.
[P11] H. de Fraysseix and P. Ossona de Mendez. Stretching of Jordan arc contact systems. In Graph Drawing, volume 2912 of Lecture Notes in Computer Science, pages 71–85. Springer Verlag, 2004. [ DOI ]
We prove that a contact system of Jordan arcs is stretchable if and only if it is extendable into a weak arrangement of pseudo-lines.
[P12] H. de Fraysseix and P. Ossona de Mendez. Contact and intersection representations. In J. Pach, editor, Graph Drawing 2004, volume 3383 of Lecture Notes in Computer Science, pages 217–227. Springer Verlag, 2005. [ DOI ]
A necessary and sufficient condition is given for a connected bipartite graph to be the incidence graph of a family of segments and points. We deduce that any 4-connected 3-colorable plane graphs is the contact graphs of a family of segments and that any 4-colored planar graph without induced C4 using 4 colors is the intersection graph of a family of straight line segments.
[P13] J. Nešetřil and P. Ossona de Mendez. Linear time low tree-width partitions and algorithmic consequences. In STOC'06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 391–400. ACM Press, 2006. [ DOI ]
Classes of graphs with bounded expansion generalize both proper minor closed classes and classes with bounded degree. For any class with bounded expansion C and any integer p there exists a constant N(C,p) so that the vertex set of any graph G∈C may be partitioned into at most N(C,p) parts, any ip parts of them induce a subgraph of tree-width at most (i-1) (actually, of tree-depth at most i, what is sensibly stronger). Such partitions are central to the resolution of homomorphism problems like restricted homomorphism dualities. We give here a simple algorithm to compute such partitions and prove that if we restrict the input graph to some fixed class C with bounded expansion, the running time of the algorithm is bounded by a linear function of the order of the graph (for fixed C and p). This result is applied to get a linear time algorithm for the subgraph isomorphism problem with fixed pattern and input graphs in a fixed class with bounded expansion. More generally, let φ be a first order logic sentence. We prove that any fixed graph property of type “∃X: (|X|≤p) ∧(G[X]⊧φ)” may be decided in linear time for input graphs in a fixed class with bounded expansion.
[P14] J. Nešetřil and P. Ossona de Mendez. Fraternal augmentations of graphs, coloration and minors. In Proceedings of the Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, volume 28 of Electronic Notes in Discrete Mathematics, pages 223–230, 2007. [ DOI ]
We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇r(G). We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings, a linear time algorithm to check subgraph isomorphism for a fixed pattern and restricted homomorphism dualities.
[P15] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Representation of planar hypergraphs by contacts of triangles. In Proceedings of Graph Drawing 2007, volume 4875/2008 of Lecture Notes in Computer Science, pages 125–136. Springer, 2008. [ DOI ]
Many representation theorems extend from planar graphs to planar hypergraphs. The authors proved in a previous paper that every planar graph has a representation by contact of triangles. We prove here that this representation result extend to planar linear hypergraphs. Although the graph proof was simple and led to a linear time drawing algorithm, the extension for hypergraphs needs more work. The proof we give here relies on a combinatorial characterization of those hypergraphs which are representable by contact of segments in the plane, We propose some possible generalization directions and open problems, related to the order dimension of the incidence posets of hypergraphs.
[P16] J. Nešetřil and P. Ossona de Mendez. From sparse graphs to nowhere dense structures: Decompositions, independence, dualities and limits. In European Congress of Mathematics, pages 135–165. European Mathematical Society, 2010. [ DOI ]
This paper surveys the recent research related to the structural properties of sparse graphs and general finite relational structures. We provide a classification of classes of finite relational structures which is defined by means of a sequence of derived classes (defined by local changes). The resulting classification is surprisingly robust and it leads to many equivalent formulations which play an important role in applications in model theory, algorithmic graph theory and structural theory. One of these equivalent formulations guarantees a quick test for a finite type decomposition in a few classes (called low tree depth decomposition). We give numerous examples from geometry and extremal graph theory and apply the result to dualities for special classes of graphs. Finally we characterize the existence of all restricted dualities in terms of limit objects induced by the convergence defined on the homomorphism order of graphs.
[P17] J. Nešetřil and P. Ossona de Mendez. Sparse combinatorial structures: Classification and applications. In R. Bhatia and A. Pal, editors, Proceedings of the International Congress of Mathematicians 2010 (ICM 2010), volume IV, pages 2502–2529, Hyderabad, India, 2010. World Scientific. [ .html ]
We present results of the recent research on sparse graphs and finite structures in the context of of contemporary combinatorics, graph theory, model theory and mathematical logic, complexity of algorithms and probability theory. The topics include: complexity of subgraph- and homomorphism- problems; model checking problems for first order formulas in special classes; property testing in sparse classes of structures. All these problems can be studied under the umbrella of classes of structures which are Nowhere Dense and in the context of Nowhere Dense – Somewhere Dense dichotomy. This dichotomy presents the classification of the general classes of structures which proves to be very robust and stable as it can be defined alternatively by most combinatorial extremal invariants as well as by algorithmic and logical terms. We give examples from logic, geometry and extremal graph theory. Finally we characterize the existence of all restricted dualities in terms of limit objects defined on the homomorphism order of graphs.
[P18] R. Ganian, P. Hliněný, J. Nešetřil, J. Obdržálek, P. Ossona de Mendez, and R. Ramadurai. When trees grow low: Shrubs and fast MSO1. In MFCS 2012, volume 7464 of Lecture Notes in Computer Science, pages 419–430. Springer-Verlag, 2012.
Recent characterization of those graphs for which coloured MSO2 model checking is fast raised the interest in the graph invariant called tree-depth. Looking for a similar characterization for (coloured) MSO1, we introduce the notion of shrub-depth of a graph class. To prove that MSO1 model checking is fast for classes of bounded shrub-depth, we show that shrub-depth exactly characterizes the graph classes having interpretation in coloured trees of bounded height. We also show that a common extension of cographs and of graphs with bounded shrub-depth — m-partite cographs (which is still below clique-width) — is well quasi-ordered by the relation “is an induced subgraph of” and therefore allows polynomial time testing of hereditary properties.

[P19] J. van den Heuvel, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. Electronic Notes in Discrete Mathematics, 49:523 – 530, 2015. [ DOI ]
[P20] J. Nešetřil and P. Ossona de Mendez. Structural limits and approximations of mappings. Electronic Notes in Discrete Mathematics, 49:531–539, 2015. [ DOI ]
We extend the general framework of structural limits from graphs and relational structures to finite structures (including function symbols). For perhaps the simplest model of this type — sets with single unary function — we determine limit objects with respect to the three main fragments of first order. In each of these cases we solve an analog of Aldous-Lyons conjecture. This builds on the experience gained when studying limits of sequences of trees.
[Top]

Books or Book Chapters

[B1] P. Ossona de Mendez. Graphes et Applications 2 (Traité IC2, série informatique et systèmes d'information), chapter 4. Représentations des graphes, pages 129–160. Hermès, 2007.
[B2] J. Nešetřil and P. Ossona de Mendez. Structural properties of sparse graphs. In Martin Grötschel and Gyula O.H. Katona, editors, Building Bridges Between Mathematics and Computer Science, volume 19 of Bolyai Society Mathematical Studies, pages 369–426. Springer, 2008.
[B3] J. Nešetřil and P. Ossona de Mendez. Sparsity (Graphs, Structures, and Algorithms), volume 28 of Algorithms and Combinatorics. Springer, 2012. 465 pages.
This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a fuzzy notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants.

This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms.

This book is related to the material presented by the first author at ECM 1998 and ICM 2010.

[B4] H. de Fraysseix and P. Ossona de Mendez. Handbook of Graph Drawing and Visualization, chapter 19 (PIGALE), pages 599–620. Discrete Mathematics and Its Applications. CRC Press, 2013.
[Top]

Softwares

[L1] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. PICTEL. Industrial Software, 1984.
PICTEL is an automatic schematic drawing software for aeronautic electrical circuits integrated into CATIA
[L2] H. de Fraysseix and P. Ossona de Mendez. Penelope. Industrial Software, 1990.
Penelope is a software dedicated to the conception and simulation of warp-weft fabrics
[L3] P. Chicourrat, H. de Fraysseix, and P. Ossona de Mendez. A hierarchical diagram drawing software. Industrial Software, 1997.
This program is an automatic SADT diagram drawing software
[L4] P. Ossona de Mendez and H. Tonneau. Pliant project. Free Software (GPL licence), 1999. [ http ]
Pliant project consists in the creation under GPL licence of a coherent and minimal software package including the base tools necessary for most users. These tools are gathered into a short source code thanks to a new language which allows to focus on what is pertinent, without preventing programmers to access any of the abstraction levels or to impose any exception to the general rules. Pliant project maybe accessed at http://fullpliant.org.
[L5] H. de Fraysseix and P. Ossona de Mendez. PIGALE: Public Implementation of a Graph Algorithm Library and Editor. Free Software (GPL licence), 2002. [ http ]
Pigale integrates a graph algorithm library written in C++ and a graph editor based on Qt and OpenGL libraries. This program is particularly intended for academic research on topological graphs. Pigale is available under GPL licence by FTP or CVS at http://sourceforge.net/projects/pigale/.
[L6] H. de Fraysseix, A. Joly, and P. Ossona de Mendez. Ariane. Software, 2003.
Ariane is a bibliographical administration software
[Top]

Others

[D1] P. Ossona de Mendez. Systèmes Mémoires Accessibles par leur Adresses ou leur Contenu. Brevet 82.07 777, 1982.
[D2] G.Th. Guilbaud, E. Coumet, P. Ossona de Mendez, and P. Rosenstiehl. Mathématique Sociale (Série “Savoir et Mémoire”). Video; Direction : M. Ferro, Réalisation : P. Gauge, 1993. AREHESS , Paris.
[D3] P. Ossona de Mendez. Orientations bipolaires. PhD thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, 1994.
The subject of this thesis is the concept of bipolar orientation of a 2-connected graph, that is an acyclic orientation with a unique source and a unique sink. The investigation starts with the abstraction of bipolar orientations in the framework of the regular oriented matroids, which is convenient field for the study of deletion, erasing and extension properties. The establishment of a perfect graph encoding any bipolar orientation of a regular matroid leads to a new characterization of graphic matroids. The planarity of a graph is then characterized in terms of the dimension of the edge partial order induced by a bipolar orientation. It is established that any two bipolar orientations of a 3-connected graph are connected by a sequence of bipolar orientations generated step by step by reversing exactly one edge. It is shown that in the case of planar graphs, there is a distributive lattice structure on the set of bipolar orientations. And the same structure holds for the 3-tree Schnyder decompositions of maximal planar graphs. In the final chapter, two representation theorems are proved: any planar graph may be represented as contact graph of families of triangles; any bipartite planar graph may be represented as contact graph of families of horizontal and vertical segments
[D4] P. Ossona de Mendez. Théorie des Graphes: Epopée et Aventures, 1996.
[D5] P. Ossona de Mendez. La société de la virtualité. Liquidation Totale, (1):29–31, 2001.
[D6] M. de Mendez, P. Ossona de Mendez, M.V. Santos, and H. Tonneau. Pliant documentation initiative. Online documentation, 2001. [ http ]
[D7] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Knowledge e-publishing tools CRAFT-1999-70979 IST 2000 52033 6.3-6.4 deliverable. confidential report, European Community, 2003. 108 pages.
[D8] P. Ossona de Mendez and H. Tonneau. The future of programming languages. Software 2.0, (100):56–58, April 2003. in Polish.
The orientation of programming languages seems to follow two main directions: The first one corresponds to a seek of major companies to get more and more power over end users, while limiting their own responsibility in a kind of “democracy” under trusteeship. The other one is a quest for independence of the users expressed, for instance, in the free software movement. While the first tendency leads to a severe limitation of programmers' possibilities and to a uniformization of “personal” softwares restricted to “macro-softwares”, the needs of the second one for coherency might lead to the introduction of another kind of operating system responsible for a language-independent compilation, which we shall call a language operating system, allowing a new level of integration: language-level integration.
[D9] AEOLUS. Structural properties of overlay computers: State of the art survey and algorithmic solutions. D1.1.1, project IP-FP6-015964 of EEC, 2006. (section 4 by P. Ossona de Mendez and J. Nešetřil). [ .pdf ]
[D10] P. Ossona de Mendez, M. Pocchiola, D. Poulalhon, J.L. Ramírez Alfonsín, and G. Schaeffer. Preface. In P. Ossona de Mendez, M. Pocchiola, D. Poulalhon, J.L. Ramírez Alfonsín, and G. Schaeffer, editors, The International Conference on Topological and Geometric Graph Theory, volume 31 of Electronic Notes in Discrete Mathematics, pages 1–4. Elsevier, 2008. [ DOI ]
[D11] F. Demangeon and P. Ossona de Mendez. Kyudo: The way of the bow. In P. Ossona de Mendez, M. Pocchiola, D. Poulalhon, J.L. Ramírez Alfonsín, and G. Schaeffer, editors, The International Conference on Topological and Geometric Graph Theory, volume 31 of Electronic Notes in Discrete Mathematics, page 17. Elsevier, 2008. Poem. [ DOI ]
[D12] L. Lovász, J. Nešetřil, P. Ossona de Mendez, and A. Schrijver. Preface. European Journal of Combinatorics, 32(7):951–953, 2011. Homomorphism and Limits special issue.
[D13] A. Machí, J. Nešetřil, P. Ossona de Mendez, and J.L. Ramírez Alfonsín. Preface. European Journal of Combinatorics, 33(3):277–278, 2012. Topological and Geometric Graph Theory special issue. [ DOI ]
[D14] P. Pajot. Le prix Abel recompense un spécialiste des mathématiques discrètes. La Recherche, pages 18–19, Juin 2012. (interview de P. Ossona de Mendez au sujet d'Endre Szemerédi).
[D15] P. Ossona de Mendez. Du théorème de Ramsey à la conjecture d'Erd os–Hajnal. Images des Mathématiques, September 2017. [ http ]
[Top]

Conference Proceedings (without refereeing)

[Top]

ArXiv Preprints

[ArXiv1] J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion III. restricted dualities. arXiv:math/0508325 [math.CO], 2005.
[ArXiv2] J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion II. algorithmic aspects. arXiv:math/0508324 [math.CO], 2005.
[ArXiv3] J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion I. decompositions. arXiv:math/0508323 [math.CO], 2005.
[ArXiv4] H. de Fraysseix, P. Rosenstiehl, and P. Ossona de Mendez. Trémaux trees and planarity. arXiv:math/0610935 [math.CO], 2006.
[ArXiv5] H. de Fraysseix and P. Ossona de Mendez. Regular embeddings of multigraphs. arXiv:math/0610937 [math.CO], 2006.
[ArXiv6] J. Nešetřil, P. Ossona de Mendez, and D.R. Wood. Characterisations and examples of graph classes with bounded expansion. arXiv:0902.3265 [math.CO], 2009.
[ArXiv7] J. Nešetřil, P. Ossona de Mendez, and X. Zhu. Colouring edges with many colours in cycles. arXiv:1108.1616 [math.CO], 2011.
[ArXiv8] J. Nešetřil and P. Ossona de Mendez. A note on Fiedler value of classes with sublinear separators. HAL, August 2012. [ http ]
The n-th Fiedler value of a class of graphs C is the maximum second eigenvalue λ2(G) of a graph G∈C with n vertices. In this note we relate this value to shallow minors and, as a corollary, we determine the right order of the n-th Fiedler value for some minor closed classes of graphs, including the class of planar graphs.

[ArXiv9] J. Nešetřil and P. Ossona de Mendez. A model theory approach to structural limits. arXiv:1303.2865 [math.CO], 2013.
[ArXiv10] J. Nešetřil and P. Ossona de Mendez. A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth). arXiv:1303.6471v2 [math.CO], October 2013.
In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on model theory and analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as “tractable cases” of a general theory. As an outcome of our theory, we provide extensions of known results and identify some new cases exhibiting specific properties suggesting that their study could be more accessible than the full general case. The second part of the paper is devoted to the study of such a case, namely limits of graphs (and structures) with bounded diameter connected components.

We prove that in this case the convergence can be “almost” studied component-wise. Eventually, we consider the specific case of limits of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of modeling we introduce here. It is also the first “intermediate class” with explicitly defined limit structures.

[ArXiv11] J. Nešetřil and P. Ossona de Mendez. Modeling limits in hereditary classes: Reduction and application to trees. arXiv:1312.0441 [math.CO], December 2013.
[ArXiv12] J. Nešetřil and P. Ossona de Mendez. On low tree-depth decompositions. arXiv:1412.1581v1 [math.CO], 2014.
[ArXiv13] J. Nešetřil and P. Ossona de Mendez. A note on circular chromatic number of graphs with large girth and similar problems. arXiv:1402.3142 [math.CO], 2014.
[ArXiv14] A.J. Goodall, J. Nešetřil, and P. Ossona de Mendez. Strongly polynomial sequences as interpretations. arXiv:1405.2449 [math.CO], May 2014.
[ArXiv15] J. Nešetřil and P. Ossona de Mendez. On first-order definable colorings. arXiv:1403.1995v2 [math.CO], June 2014.
We address the problem of characterizing H-coloring problems that are first-order definable on a fixed class of relational structures. In this context, we give several characterizations of a homomorphism dualities arising in a class of structure.

[ArXiv16] J. Nešetřil and P. Ossona de Mendez. Cluster analysis of local convergent sequences of structures. arXiv:1510.07788 [math.CO], 2015.
[ArXiv17] J. Nešetřil and P. Ossona de Mendez. First-order limits, an analytical perspective. arXiv:1503.07627 [math.CO], 2015.
[ArXiv18] P. Charbit, L. Hosseini, and P. Ossona de Mendez. Limits of structures and the example of tree-semilattices. arXiv:1505.03037 [math.CO], 2015.
The notion of left convergent sequences of graphs introduced by Lovász et al. (in relation with homomorphism densities for fixed patterns and Szemerédi's regularity lemma) got increasingly studied over the past 10 years. Recently, Nešetřil and Ossona de Mendez introduced a general framework for convergence of sequences of structures. In particular, the authors introduced the notion of QF-convergence, which is a natural generalization of left-convergence. In this paper, we initiate study of QF-convergence for structures with functional symbols by focusing on the particular case of tree semi-lattices. We fully characterize the limit objects and give an application to the study of left convergence of m-partite cographs, a generalization of cographs.

[ArXiv19] P. Ossona de Mendez, S. Oum, and D.R. Wood. Defective colouring of graphs excluding a subgraph or minor. arXiv:1611.09060 [math.CO], 2016.
Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3-coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015) proved that graphs with no Kt+1-minor can be t-coloured so that each colour class induces asubgraph of bounded maximum degree. We prove a common generalisation of these theorems with a weaker assumption about excluded subgraphs. This result leads to new defective colouring results for several graph classes, including graphs with linear crossing number, graphs with given thickness, graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs excluding a complete bipartite graph as a topological minor.
[ArXiv20] J. Nešetřil and P. Ossona de Mendez. Existence of modeling limits for sequences of sparse structures. arXiv:1608.00146 [math.CO], 2016.
[ArXiv21] J. Nešetřil and P. Ossona de Mendez. Limits of mappings. arXiv:1602.07147 [math.CO], 2016.
[ArXiv22] J. Nešetřil and P. Ossona de Mendez. Towards a characterization of universal categories. arXiv:1608.01112 [math.CT], 2016.
[ArXiv23] L. Hosseini and P. Ossona de Mendez. Treeable graphings are local limits of finite graphs. arXiv:1601.05580 [math.CO], 2016.
Let G be a graphing, that is a Borel graph defined by d measure preserving involutions. We prove that if G is treeable then it arises as the local limit of some sequence (Gn)n&isin;ℕ of graphs with maximum degree at most d. This extends a result by Elek [G. Elek, Note on limits of finite graphs, Combinatorica 27 (2007)] (for G a treeing) and consequently extends the domain of the graphings for which Aldous–Lyons conjecture is known to be true.
[ArXiv24] J. van den Heuvel, P. Ossona de Mendez, D. Quiroz, R. Rabinovich, and S. Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. arXiv:1602.09052 [math.CO], 2016.
[ArXiv25] J. Chalopin, L. Esperet, Z. Li, and P. Ossona de Mendez. Restricted frame graphs and a conjecture of Scott. arXiv:1406.0338v2 [math.CO], 2016.
[ArXiv26] G. Joret, P. Micek, P. Ossona de Mendez, and V. Wiechert. Nowhere dense graph classes and dimension. arXiv:1708.05424v1[math.CO], 2017.
Nowhere dense graph classes provide one of the least restrictive notions of sparsity for graphs. Several equivalent characterizations of nowhere dense classes have been obtained over the years, using a wide range of combinatorial objects. In this paper we establish a new characterization of nowhere dense classes, in terms of poset dimension: A monotone graph class is nowhere dense if and only if for every h ≥1 and every ε> 0, posets of height at most h with n elements and whose cover graphs are in the class have dimension O(nε).

[ArXiv27] S. Kreutzer, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz. Algorithmic properties of sparse digraphs. arxiv:1707.01701 [cs.DM], 2017.
The notions of bounded expansion and nowhere denseness have been applied very successfully in algorithmic graph theory. We study the corresponding notions of directed bounded expansion and nowhere crownfulness on directed graphs. We show that red many of the algorithmic tools that were developed for undirected bounded expansion classes can, with some care, also be applied in their directed counterparts, and thereby we highlight a rich algorithmic structure theory of directed bounded expansion classes. More specifically, we show that the directed Steiner tree problem is fixed-parameter tractable on any class of directed bounded expansion parameterized by the number k of non-terminals plus the maximal diameter s of a strongly connected component in the subgraph induced by the terminals. Our result strongly generalizes a result of Jones et al., who proved that the problem is fixed parameter tractable on digraphs of bounded degeneracy if the set of terminals is required to be acyclic. We furthermore prove that for every integer r≥1, the distance-r dominating set problem can be approximated up to a factor O(logk) and the connected distance-r dominating set problem can be approximated up to a factor O(k⋅logk) on any class of directed bounded expansion, where k denotes the size of an optimal solution. If furthermore, the class is nowhere crownful, we are able to compute a polynomial kernel for distance-r dominating sets. Polynomial kernels for this problem were not known to exist on any other existing digraph measure for sparse classes.

[ArXiv28] R. Ganian, P. Hliněný, J. Nešetřil, J. Obdržálek, and P. Ossona de Mendez. Shrub-depth: Capturing height of dense graphs. arxiv:1707.00359 [cs.LO], 2017.
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 analogously useful "depth" notion also for dense graphs (say; one which is stable under graph complementation)? To this end we introduced, in a 2012 conference paper, the notion of shrub-depth of a graph class which is related to the established notion of clique-width in a similar way as tree-depth is related to tree-width. Since then shrub-depth has been successfully used in several research papers. Here we provide an in-depth review of the definition and basic properties of shrub-depth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrub-depth to give a characterization of the lower ω levels of the MSO1 transduction hierarchy of simple graphs.

[ArXiv29] J. Gimbel, P. Ossona de Mendez, and P. Valtr. Obstacle numbers of planar graphs. arXiv:1706.06992 [math.CO], 2017.
Given finitely many polygonal obstacles O1,...,Ok in the plane and a set P of points in general position and not in any obstacle, the visibility graph of P with obstacles O1,...,Ok is the (geometric) graph with vertex set P, where two vertices are adjacent if the straight line segment joining them intersects no obstacle.

The obstacle number of a graph G is the smallest number k of polygonal obstacles O1,...,Ok such that G is the visibility graph of a set of points with obstacles O1,...,Ok. If G is planar, we define the planar obstacle number of G by further requiring that the visibility graph has no crossing edges (hence that it is a planar geometric drawing of G). In this paper, we prove that the maximum planar obstacle number of a planar graph of order n is n-3, the maximum being attained (in particular) by maximal bipartite planar graphs. This displays a significant difference with the standard obstacle number, as we prove that the obstacle number of every bipartite planar graph of order at least 3 is 1. This last result is a consequence of a similar statement for intersection graphs of straight line segments in two directions.

[ArXiv30] S.A. Amiri, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz. Distributed domination on graph classes of bounded expansion. arXiv:1702.02848 [cs.DC], 2017.
[Top]

KAM--DIAMATIA Series

[KAM1] H. de Fraysseix and P. Ossona de Mendez. A short proof of a Gauss problem. Technical Report 97-358, KAM-DIMATIA Series, 1997.
[KAM2] H. de Fraysseix and P. Ossona de Mendez. Stretchability of Jordan Arc Contact Systems. Technical Report 98-387, KAM-DIMATIA Series, 1998.
[KAM3] J. Nešetřil and P. Ossona de Mendez. Colorings and homomorphisms of minor closed classes. Technical Report 2001-523, KAM-DIMATIA Series, 2001.
[KAM4] J. Nešetřil and P. Ossona de Mendez. Folding. Technical Report 2002-089, KAM-DIMATIA Series, 2002.
[KAM5] J. Nešetřil and P. Ossona de Mendez. Cuts and bounds. Technical Report 2002-097, KAM-DIMATIA Series, 2002.
[KAM6] J. Nešetřil and P. Ossona de Mendez. Tree depth, subgraph coloring and homomorphism bounds. Technical Report 2004-656, KAM-DIMATIA Series, 2004.
[KAM7] P. Ossona de Mendez and P. Rosenstiehl. Encoding pointed maps by double occurrence words. Technical Report 2005-752, KAM-DIMATIA Series, 2005.
[KAM8] J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion III. Restricted dualities. Technical Report 2005-741, KAM-DIMATIA Series, 2005.
We study restricted homomorphism dualities in the context of classes with bounded expansion. This presents a generalization of restricted dualities obtained earlier for bounded degree graphs and also for proper minor closed classes. This is related to distance coloring of graphs and to the “approximative version” of Hadwiger conjecture.
[KAM9] J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion II. Algorithmic aspects. Technical Report 2005-740, KAM-DIMATIA Series, 2005.
Classes of graphs with bounded expansion are a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇r(G). These classes are also characterized by the existence of several partition results such as the existence of low tree-width and low tree-depth colorings. These results lead to several new linear time algorithms, such as an algorithm for counting all the isomorphs of a fixed graph in an input graph or an algorithm for checking whether there exists a subset of vertices of a priori bounded size such that the subgraph induced by this subset satisfies some arbirtrary but fixed first order sentence. We also show that for fixed p, computing the distances between two vertices up to distance p may be performed in constant time per query after a linear time preprocessing. We also show, extending several earlier results, that a class of graphs has sublinear separators if it has sub-exponential expansion. This result result is best possible in general.
[KAM10] J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion I. Decompositions. Technical Report 2005-739, KAM-DIMATIA Series, 2005.
We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇r(G). For these classes we prove the existence of several partition results such as the existence of low tree-width and low tree-depth colorings. This generalizes and simplifies several earlier results (obtained for minor closed classes).
[KAM11] J. Nešetřil and P. Ossona de Mendez. Linear time low tree-width partitions and consequences. Technical Report 2006-763, KAM-DIMATIA Series, 2006.
[KAM12] J. Nešetřil and P. Ossona de Mendez. Induced matchings and induced paths in graphs. Technical Report 2007-810, KAM-DIMATIA Series, 2007.
[KAM13] J. Nešetřil and P. Ossona de Mendez. Structural properties of sparse graphs. Technical Report 2008-863, KAM-DIMATIA Series, 2008.
[KAM14] J. Nešetřil and P. Ossona de Mendez. First order properties on nowhere dense structures. Technical Report 2008-865, KAM-DIMATIA Series, 2008.
[KAM15] J. Nešetřil, P. Ossona de Mendez, and D.R. Wood. Characterisations and examples of graph classes with bounded expansion. Technical Report 2009-909, KAM-DIMATIA Series, 2009. [ .pdf ]
[KAM16] J. Nešetřil and P. Ossona de Mendez. On nowhere dense graphs. Technical Report 2009-928, KAM-DIMATIA Series, 2009. [ .pdf ]
[KAM17] J. Nešetřil, P. Ossona de Mendez, and X. Zhu. Colouring edges with many colours in cycles. Technical Report 2011-1008, KAM-DIMATIA Series, 2011. [ .pdf ]
[KAM18] J. Nešetřil and P. Ossona de Mendez. A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth). Technical Report 2013-573, KAM-DIMATIA Series, 2013.
In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on model theory and analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as “tractable cases” of a general theory. As an outcome of our theory, we provide extensions of known results and identify some new cases exhibiting specific properties suggesting that their study could be more accessible than the full general case. The second part of the paper is devoted to the study of such a case, namely limits of graphs (and structures) with bounded diameter connected components.

We prove that in this case the convergence can be “almost” studied component-wise. Eventually, we consider the specific case of limits of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of modeling we introduce here. It is also the first “intermediate class” with explicitly defined limit structures.

[KAM19] J. Nešetřil and P. Ossona de Mendez. On first-order definable colorings. Technical Report 2014-609, IUUK-CE-ITI Series, 2014.
In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on model theory and analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as “tractable cases” of a general theory. As an outcome of our theory, we provide extensions of known results and identify some new cases exhibiting specific properties suggesting that their study could be more accessible than the full general case. The second part of the paper is devoted to the study of such a case, namely limits of graphs (and structures) with bounded diameter connected components.

We prove that in this case the convergence can be “almost” studied component-wise. Eventually, we consider the specific case of limits of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of modeling we introduce here. It is also the first “intermediate class” with explicitly defined limit structures.

[KAM20] J. Nešetřil and P. Ossona de Mendez. A note on circular chromatic number of graphs with large girth and similar problems. Technical Report 2014-606, IUUK-CE-ITI Series, 2014.
In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on model theory and analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as “tractable cases” of a general theory. As an outcome of our theory, we provide extensions of known results and identify some new cases exhibiting specific properties suggesting that their study could be more accessible than the full general case. The second part of the paper is devoted to the study of such a case, namely limits of graphs (and structures) with bounded diameter connected components.

We prove that in this case the convergence can be “almost” studied component-wise. Eventually, we consider the specific case of limits of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of modeling we introduce here. It is also the first “intermediate class” with explicitly defined limit structures.

[KAM21] J. Nešetřil and P. Ossona de Mendez. A distributed low tree-depth decomposition algorithm for bounded expansion classes. Technical Report 2015-623, IUUK-CE-ITI Series, 2015.
In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on model theory and analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as “tractable cases” of a general theory. As an outcome of our theory, we provide extensions of known results and identify some new cases exhibiting specific properties suggesting that their study could be more accessible than the full general case. The second part of the paper is devoted to the study of such a case, namely limits of graphs (and structures) with bounded diameter connected components.

We prove that in this case the convergence can be “almost” studied component-wise. Eventually, we consider the specific case of limits of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of modeling we introduce here. It is also the first “intermediate class” with explicitly defined limit structures.

[KAM22] J. Nešetřil and P. Ossona de Mendez. Cluster analysis of local convergent sequences of structures. Technical Report 2016-643, IUUK-CE-ITI Series, 2016.
[KAM23] J. Nešetřil and P. Ossona de Mendez. Structural sparsity. Technical Report 2016-642, IUUK-CE-ITI Series, 2016.
[KAM24] J. Nešetřil and P. Ossona de Mendez. Towards a characterization of universal categories. Technical Report 2016-641, IUUK-CE-ITI Series, 2016.
[Top]

ALCOM Reports

[ALCOM1] M. Bousset, H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Envahir sans encercler l'ennemi. Technical report, ALCOM 90-72, 1990.
[ALCOM2] M. Bousset, H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Posters on the automatic generation of layouts of technological networks. Technical report, ALCOM 91-62, 1991.
[ALCOM3] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Partial orders and orientation. ALCOM journal, 1992.
[ALCOM4] P. Ossona de Mendez. Partial angle assignments compatible with an orientation of a plane graph. Technical report, ALCOM II-027, 1993.
[ALCOM5] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Bipolar orientations revisited. Technical report, ALCOM II-025, 1993.
[ALCOM6] H. de Fraysseix, P. Ossona de Mendez, and J. Pach. Representation of planar graphs by segments. Technical report, ALCOM II-031, 1993.
[ALCOM7] H. de Fraysseix, P. Ossona de Mendez, and J. Pach. A streamlined depth-first search algorithm revisited. Technical report, ALCOM-II-030, 1993.
[ALCOM8] H. de Fraysseix and P. Ossona de Mendez. Planarity and edge poset dimension. Technical report, ALCOM II-024, 1993.
[ALCOM9] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Technical report, ALCOM report, 1994.
[Top]

CAMS Series

[CAMS1] H. de Fraysseix and P. Ossona de Mendez. On intersection graphs of Jordan arcs. Technical Report 146, CAMS, 1997.
[CAMS2] H. de Fraysseix and P. Ossona de Mendez. A short proof of a Gauss problem. Technical Report 145, CAMS, 1997.
[CAMS3] P. Chicourrat, H. de Fraysseix, and P. Ossona de Mendez. A hierarchical diagram drawing software. Technical Report 147, CAMS, 1997.
Intermediate between texts and pictures, diagrams are a natural presentation scheme for computer-human interface. For instance, hierarchical diagrams are an usual tool for engineering and documentation of complex systems. Although the handmade documentation is restricted to particular views of the system, an automatic diagram drawer allows the production of query-driven functional subsystems.
[CAMS4] H. de Fraysseix and P. Ossona de Mendez. On topological aspects of orientations. Technical Report 158, CAMS, 1998.
[CAMS5] P. Ossona de Mendez and P. Rosenstiehl. Connected permutations and hypermaps. Technical Report 183, CAMS, 1999. [ .dvi.gz ]
A link is developed between the orbits of a bi-generated permutation group and the components of a permutation p over an interval of N, these components corresponding to sub-intervals fixed by p. Several bijections are established between combinatorial families whose equi-cardinality were considered as mysterious by the literature so far. A coding of pointed maps and hypermaps follows.
[CAMS6] P. Ossona de Mendez. The reduced genus of a multigraph. Technical Report 174, CAMS, 1999.
[CAMS7] P. Ossona de Mendez. Geometric realization of simplicial complexes. Technical Report 178, CAMS, 1999.
[CAMS8] P. Ossona de Mendez. 3-colorability and contacts of segments. Technical Report 171, CAMS, 1999.
Using a previous result on planar graph representation, we shall prove that vertex 3-colorability is NP-complete for contact graphs of segments even if no 3 segments may share a contact point, if the segments lye in 4-directions and if the representation is given.
[CAMS9] M. Las Vergnas and P. Ossona de Mendez. On barycentric representation of graphs. Technical Report 182, CAMS, 1999.
[CAMS10] H. de Fraysseix and P. Ossona de Mendez. Stretchability of Jordan arc contact systems. Technical Report 172, CAMS, 1999.
[CAMS11] H. de Fraysseix and P. Ossona de Mendez. Connectivity of planar graphs. Technical Report 173, CAMS, 1999.
[Top]

Abstracts in Conference Proceedings

[r1] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Bipolar orientations revisited. In Fifth Franco-Japanese Days on Combinatorics and Optimization, 1992. abstract.
[r2] P. Ossona de Mendez. The Plane Bipolar Orientations' Lattice. In Sixth Franco-Japanese Days on Combinatorics and Optimization, 1993. abstract.
Given a biconnected graph G and an oriented edge e=(s,t) of G, a bipolar orientation based on the orientation of e (or e-bipolar orientation of G) is an acyclic orientation of the edges of G having s as a unique source and t as a unique sink. Bipolar orientations are closely related to connexity and planarity. They have been extensively used to perform graph drawing of planar graphs, upward drawings and testing graph planarity. In the planar case, the angle graphe A(G) of G is defined as the vertex/face adjacency graph related to an embedding of G. Then, the e-bipolar orientations of G are in bijection with the edge 2-colorations of A(G) satisfying local conditions. From the 2-coloration corresponding to an e-bipolar orientation, the 2-coloration corresponding to any other e-bipolar orientation may be obtained by inverting the edge coloration over alternating cycles. An edge 2-coloration of A(G) is equivalent to an orientation of the edges of A(G). When considering this orientation, alternating cycles of A(G) correspond to oriented circuits. The transformation from one e-bipolar orientation O into another e-bipolar orientation O' corresponds (in A(G)) to the inversion of a circuit. This circuit may be expressed as the sum of clockwise oriented faces of A(G) using integer coefficients. All or part of these coefficients might be negative integers. If all of them are positive, O is said to be smaller than O'. If the graph is 3-connected, the so defined partial order is a distributive lattice on the e-bipolar orientations' set of a plane graph G. That means that two uncomparable e-bipolar orientations O and O' have an infimum OO' (a greatest e-bipolar orientation smaller than both O and O') and a supremum OO'. This lattice is distributive as the infimum and supremum operators are distributive with one another. Moreover, the minimum and maximum e-bipolar orientations of the lattice may be expressed using a very simple linear-time algorithm. The Hasse diagram of the lattice, that is the graph whose vertices are the e-bipolar orientations of G and whose (oriented) edges correspond to the immediate-sucessor relation, is the adjacency graph of the e-bipolar orientations of G (two orientations being adjacent if they differ by the orientation of an unique edge) with an appropriate orientation.
[r3] P. Ossona de Mendez. On Lattice Structures induced by Orientations. In Proc. of Graph Drawing '93, pages 33–34, 1993. abstract.
[r4] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. In proc. of Graph Drawing '93, pages 37–38, 1993. abstract.
[r5] H. de Fraysseix and P. Ossona de Mendez. New problems and conjectures. In Prague Midsummer Combinatorial Workshop, volume 93-254, pages 8–10, 1993. abstract.
[r6] H. de Fraysseix and P. Ossona de Mendez. On Regular Orientations. In Prague Midsummer Combinatorial Workshop, pages 9–13, 1994. abstract.
[r7] H. de Fraysseix and P. Ossona de Mendez. Some augmentation problems. In Effiziente Algorithmen, volume 34/1994, page 11, 1994. abstract.
[r8] P. Ossona de Mendez. Representation of Hypergraphs by Contact of Segments. In Conférence Internationale “Graphe et Combinatoire”, 1995. abstract.
[r9] H. de Fraysseix and P. Ossona de Mendez. 9 Problems from Paris Group as presented by Hubert and Patrice – Selected problems from the Atelier de Taxiplanie. In Prague Midsummer Combinatorial Workshop, pages 28–31, 1995. abstract.
[r10] H. de Fraysseix and P. Ossona de Mendez. Intersection graphs of Jordan arcs. In Discrete and Computational Geometry : Ten Years Later, page 14, 1995.
[r11] H. de Fraysseix, T. Matsumoto, P. Ossona de Mendez, and P. Rosenstiehl. Regular Orientations and Graph Drawing. In Third Slovenian International Conference in Graph Theory, pages 12–13, 1995. abstract.
[r12] H. de Fraysseix and P. Ossona de Mendez. Distributive Lattices on Planar Graphs. In T. Nishizeki, R. Tamassia, and D. Wagner, editors, Graph Algorithms and Applications, volume 219 of Dagsthul-Seminar-Report, page 30, 1998. abstract.
[r13] H. Crapo, P. Ossona de Mendez, and P. Rosenstiehl. Permutation coding of maps on surfaces. In János Bolyai Mathematical Society, editor, Paul Erdös and his Mathematics, abstracts of invited talks, pages 53–54, 1999.
[r14] P. Ossona de Mendez and P. Rosenstiehl. Coding properties of Breadth-First Search orderings. In 6ème Colloque International de Théorie des Graphes, volume 5 of Electronic Notes in Discrete Mathematics, pages 253–255, 2000. [ DOI ]
[r15] H. de Fraysseix and P. Ossona de Mendez. Lower bounds on sets supporting Fáry drawings. In O. Pangrac, editor, Graph Theory Day V, volume 2001-539 of KAM Series, pages 35–37, 2001. [ .ps ]
[r16] P. Ossona de Mendez and P. Rosenstiehl. Connected permutations and hypermaps. In Prague Midsummer Combinatorial Workshop VIII, number 2002-561 in KAM-DIMATIA Series, pages 13–18, 2002. abstract.
[r17] P. Ossona de Mendez and P. Rosenstiehl. Balanced bicoloration, homomorphism and graph dimension. In M. Bálek, editor, Prague Midsummer Combinatorial Workshop X, number 2004-682 in KAM-DIMATIA Series, pages 47–53, 2004. abstract.
[r18] J. Nešetřil and P. Ossona de Mendez. How many colors may we require? In M. Mareš, editor, Prague Midsummer Combinatorial Workshop IX, number 2004-686 in KAM-DIMATIA Series, pages 27–30, 2004. abstract.
[r19] J. Nešetřil and P. Ossona de Mendez. The grad of a graph and classes with bounded expansion. In A. Raspaud and O. Delmas, editors, 7th International Colloquium on Graph Theory, volume 22 of Electronic Notes in Discrete Mathematics, pages 101–106. Elsevier, 2005. [ DOI ]
We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇r(G). We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings and homomorphism dualities.
[r20] J. Nešetřil and P. Ossona de Mendez. Aspects algorithmiques des classes d'expansion bornée. In L. Esperet, editor, 7e Journées Graphes et Algorithmes, volume 1372–05, pages 55–58. LaBRI – Université Bordeaux I, 2005. [ www: ]
Classes of graphs with bounded expansion are a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇r(G). These classes are also characterized by the existence of several partition results such as the existence of low tree-width and low tree-depth colorings. These results lead to several new linear time algorithms, such as an algorithm for counting all the isomorphs of a fixed graph in an input graph or an algorithm for checking whether there exists a subset of vertices of a priori bounded size such that the subgraph induced by this subset satisfies some arbirtrary but fixed first order sentence. We also show that for fixed p, computing the distances between two vertices up to distance p may be performed in constant time per query after a linear time preprocessing. Moreover, classes with expansion bounded by a sub-exponential function have sublinear separators.
[r21] J. Nešetřil and P. Ossona de Mendez. Low tree-depth partitions of classes with bounded expansion. In J. Kára, editor, Midsummer Combinatorial Workshop 2005 and DIMACS, DIMATIA, Rényi Workshop 2005, volume 2006-770 of KAM Series, pages 76–81, 2006.
[r22] J. Nešetřil and P. Ossona de Mendez. Finding high girth chromatic subgraphs in high chromatic sparse graphs. In M. Tesar, editor, Workshop on Coverings and Colorings 2009, volume 2009-929 of KAM-DIMATIA Series, pages 11–12, 2009.
[r23] J. Nešetřil and P. Ossona de Mendez. Counting homomorphisms to sparse graphs. In J. Nešetřil and A. Raspaud, editors, European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), volume 34, pages 393–397, 2009. [ DOI ]
[Top]

In preparation