Bibliographie

Cette page a été générée en partie grâce à bibtex2html.

Résumés: Cacher/Montrer/Montrer sélectivement.





[Haut de Page]

Revues (avec comité de lecture)

[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.
Un graphe biparti planaire G étant donné, nous assignons à ses sommets des segments horizontaux et verticaux, de telle sorte que (a) deux segments n'aient jamais de point interieur commun, (b) deux segments aient un point commun si et seulement si les sommets correspondants sont adjacents dans G.
[A2] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Combinatorics, Probability and Computing, 3:233–246, 1994.
Nous prouvons que tout graphe plan peut être représenté par un système de triangles en contact, i.e. par une collection de disques triangulaires disjoints sauf en leur points de contact, tout point de contact étant le sommet d'exactement un triangle. Nous en déduisons des représentations par contacts d'objets en forme de T et de Y, respectivement. De plus, nous montrons que les représentations par contacts de triangles d'un graphe maximal planaire sont en bijection avec les décompositions de Schnyder du graphe en trois arbres.
[A3] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. Bipolar orientations revisited. Discrete Applied Mathematics, 56:157–179, 1995. [ DOI ]
Les orientations acycliques possédant une seule source et un seul puits – connues sous le nom d'orientations bipolaires – apparaissent dans nombre d'algorithmes de graphes et spécialement dans ceux de tracé. Les propriétés fondamentales de ces orientations sont explorées, en termes de circuits, de cocircuits, mais aussi d'“angles” dans le cas planaire. Nous donnons des preuves orignales simples des résulats classiques; les nouveaux résultats concernent l'extension d'une orientation partielle, l'existence d'arêtes effaables et/ou contractibles, et les transitions continues entre orientations bipolaires.
[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.
Nous explicitons un algorithme en temps O(|V(G)|) assignant aux sommets d'un graphe biparti plan des sommets horizontaux et verticaux de telle sorte que (i) deux segments n'aient jamais de point interieur commun, (ii) deux segments aient un point commun si et seulement si les sommets correspondants sont adjacents dans G. Comme corollaire, nous obtenons un renforcement du théorème de Ringel and Petrovič: les arêtes de tout graphe maximal biparti plan G de face extérieure bwb'w' peuvent être coloriées en deux couleurs, de telle sorte que les classes forme des arbres couvrants de G-b et G-b', respectivement. De plus, une telle coloration peut être calculée en temps linéaire. Notre méthode est basée sur un nouvel algorithme en temps linéaire d'orientation bipolaire d'un graphe 2-connexe plan.
[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.
Nous prouvons que tout graphe plan peut être représenté par un système de triangles en contact, i.e. par une collection de disques triangulaires disjoints sauf en leur points de contact, tout point de contact étant le sommet d'exactement un triangle. Nous en déduisons des représentations par contacts d'objets en forme de T et de Y, respectivement. De plus, nous montrons que les représentations par contacts de triangles d'un graphe maximal planaire sont en bijection avec les décompositions de Schnyder du graphe en trois arbres.
[A6] H. de Fraysseix and P. Ossona de Mendez. Planarity and edge poset dimension. European Journal of Combinatorics, 17:731–740, 1997. [ DOI ]
Les différents domaines des mathématiques discrètes ont apporté des caractérisation intrinsèquement différentes de la planarité. Celle ci peut être exprimée en termes topologiques, combinatoires, algébriques ou par les propriétés d'arbres de recherche. Plus récemment, Schnyder a relié la planarité avec la théorie des ordres partiels. Les orientations acycliques et l'ordre partiel associé sur les arêtes amène une nouvelle caractérisation de la planarité qui décrit, de plus, tous les plongements planaires possibles. Nous démontrons que les graphes plans bipolairement orientés sont en bijection avec les ordres partiels N-free de dimension 2. Nous caractérisons également la planarité en termes de 2-colorabilité d'un graphe, et fournissons une preuve courte d'un précédent résultat sur les treillis planaires.
[A7] H. de Fraysseix and P. Ossona de Mendez. On a Characterization of Gauss Codes. Discrete & Computational Geometry, 22(2):287–295, 1999. [ DOI ]
La traversée d'un courbe simple auto-sécante du plan ayant des points de multiplicité au plus deux définit une suite à double occurences, le code de Gauss de la courbe. En utilisant l'opération de “D-switch”, nous donnons une nouvelle caractérisation simple de ces séquences et en déduisons une preuve simple et auto-suffisante de la caractérisation de Rosenstiehl.
[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.
Une famille d'arcs de Jordan telle que deux arcs ne soient nulle part tangents definit un hypergraphe dont les sommets sont les arcs et dont les arêtes sont les points d'intersection. Nous dirons que l'hypergraphe a une représentation forte par intersection et, si chaque point d'intersection est intérieur à au plus un arc, nous dirons que l'hypergraphe a une représentation forte par contact. Nous caractérisons tout d'abord les hypergraphes ayant une représentation forte par contact et en déduisons des conditions suffisantes pour qu'un graphe simple planaire ait une représentation forte par intersection. Ensuite, à l'aide du théorème des quatres couleurs, nous prouvons qu'une large classe de graphes simples planaires ont une représentation forte par intersection.
[A9] H. de Fraysseix and P. Ossona de Mendez. On topological aspects of orientations. Discrete Mathematics, 229(1-3):57–72, 2001. [ DOI ]
Nous étudions deux classes de graphes planaires: les graphes maximaux planaires (i.e. graphes polyhedraux, triangulations) et les graphes planaires bipartis maximaux (i.e. graphes bipartis planaires quadrangulés). Nous considérons les orientations de ces graphes possédant un degré entrant constant sur l'ensemble des sommets internes. Nous rappelons ou démontrons de nouvelles relations fondamentales entre ces orientations, des décompositions particulières en arbres et les orientations bipolaires. En particulier, ces relations engendrent des algorithmes en temps linéaire. Grce à ces orientations, nous donnons de nouvelles caractérisations de la 4-connexité des graphes maximaux planaires et de la 3-connexité des graphes planaires induisant des algorithmes simples en temps linéaire.
[A10] H. de Fraysseix and P. Ossona de Mendez. Connectivity of planar graphs. Journal of Graph Algorithms and Applications, 5(5):93–105, 2001.
Nous donnons ici trois algorithmes simples en temps linéaire opérant sur les graphes planaires: un test de 4-connexité pour les graphes maximaux planaires, un algorithme énumérant les triangles et un test de 3-connexité. Bien que tous ces problèmes aient déjà reu des solutions en temps linéaire, les algorithmes proposés présentent l'intérêt de la simplicité et de l'efficacité. Ces algorithmes sont basés sur de nouveaux résultats théoriques.
[A11] P. Ossona de Mendez. Realization of posets. Journal of Graph Algorithms and Applications, 6(1):149–153, 2002.
Nous prouvons un théorème de représentation d'ordre partiel très général et, comme corollaire, déduisons que tout complexe simplicial abstrait S peut être réalisé géométriquement dans l'espace Euclidien de dimension (d-1), o d=P(S) est la dimension de Dushnik-Miller de l'ordre partiel d'inclusion des faces de 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.
Nous relions le nombre chromatique acyclique et “étoilé” d'un graphe au nombre chromatique de ses mineurs. En conséquence, nous montrons que l'ensemble des graphes planaires sans triangles est borné par la relation d'homomorphisme par un graphe sans triangle. Nous améliorons également, pour les graphes planaires, la meilleure borne connue sur le nombre chromatique étoilé de 80 à 30. Notre méthode se généralise à toutes les classes fermées par mineur et offre une nouvelle vision de la conjecture de Hadwiger.
[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 ]
Nous donnons une caractérisation des graphes DFS coarbre-critiques qui est central à l'algorithme en temps linéaire de recherche d'une configuration de Kuratowski dans un graphe non planaire mis en œuvre dans PIGALE (Public Implementation of a Graph Algorithm Library and Editor) par les auteurs, et en déduisons un algorithme de recherche d'une configuration de Kuratowski dans un graphe DFS coarbre-critique.
[A14] P. Ossona de Mendez and P. Rosenstiehl. Transitivity and connectivity of permutations. Combinatorica, 24(3):487–502, 2004. [ DOI ]
Il était connu depuis des années, spécialement en physique quantique, que les permutations connexes (également appelées permutations indécomposables) de [0;n], i.e. les permutations telles que, pour tout i<n, il existe j>i tel que p(j)<i, sont en nombre égal à celui des hypercartes pointées de taille n, i.e. que les paires transitives (p,q) de permutation sur un ensemble de cardinal n possédant un élément distingué. Cet article établit une bijection naturelle entre ces deux familles. Un codage des cartes s'ensuit.
[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 ]
La dimension d'un graphe, c'est-à-dire la dimension de son ordre partiel d'incidence, s'est imposé comme étant un pont majeur entre ordres partiels et graphes. Quoique permettant une élégante caractérisation de la planarité, cette dimension se comporte mal avec les homomorphismes. Nous introduisons la dimension universelle d'un graphe G comme étant la dimension maximale d'un graphe ayant un homomorphisme vers G. La dimension universelle, qui est clairement homomorphisme monotone, est liée à l'existence de certaines bicolorations équilibrées des sommets au sein d'un réaliseur. De nouveaux résultats non triviaux reliant la dimension (standard) d'un graphe sont déduites de notre étude de la dimension universelle, concernant en particulier des propriétés chromatiques et extrémales.
[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 ]
Nous considérons l'ordre de coloration (ou d'homomorphisme) sur l'ensemble des graphes finis. Cet ordre peut être vu comme un treillis qui, néanmoins, est loin d'être complet. Dans cet article, nous étudions les bornes, les suprema et les éléments maximaux de certaines classes C fréquemment étudiées (graphes à degrés bornés, graphes dégénérés et graphes définis par un ensemble de mineurs exclus). Nous relions ces extrema aux antichaines de sous classes K de C. Nous déterminons toutes les antichaines de la classe des graphes dégénérés. En ce qui concerne les classes des graphes de degrés uniformément bornés, le problème semble particulièrement difficile, ainsi que le laissait présager le fait que ces classes n'ont pas de supremum. Nous notons une différence fondamentale de comportement entre graphes orientés et non orientés, à partir des travaux récents de C. Tardif et J. Nešetřil. Nous considérons également les classes fermées par mineurs et survolons des résultats récents obtenus par les auteurs. Cette approche s'avère étonnamment reliée à la conjecture de Hadwiger et suggère de nouveaux problèmes.
[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.
Nous montrons que les cartes pointes m artes sont en bijection avec les mots double occurrences standards (m+1) symboles.
[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 ]
Nous dfinissons les notions de profondeur d'arbre et nombre chromatique suprieur d'un graphe et montrons leurs pertinences aux phnomnes local-global lis aux partitions de graphe. En particulier, nous montrons que le nombre chromatique suprieur coincide avec la fonction maximale pouvant tre localement exige dans une coloration borne au sein d'une classe ferme par mineurs. La forte inter-relation de ces notions trouve une application dans la dtermination d'une borne pour les classes fermes par mineurs satisfaisant des conditions locales. En particulier, nous prouvons le rsulat suivant: Pour tout graphe M et tout ensemble fini F de graphes connexes, il existe un graphe (universel) U = U(M, F) ∈Forb(F) tel que tout graphe GForb(F) n'ayant pas M comme mineur satisfasse GU (i.e. G est homomorphique U). Cela rsoud le principal problme ouvert conernant les dualits restreintes pour les classes fermes par mineur; comme application, cela implique que les nombres chromatiques des puissance impaires exactes des graphes d'une classe propre ferme par mineur sont borns. Nous gnralisons galement le thorme de dcomposition de 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 ]
Nous définissons le repliement d'un graphe orienté comme étant une coloration (ou un homomorphisme) injective sur toute section finissante d'une certaine profondeur. Alors que les repliements généraux sont aussi complexes que les homomorphismes, ils représentent pour certaines classes un outil performant d'étude des homomorphismes et des colorations. Notre résultat principal affirme l'existence, pour toute classe propre C fermée par mineurs, d'un repliement (de profondeur prescrite) utilisant un nombre fixé de couleurs. Nous en déduisons l'existence, pour toute classe propre C fermée par mineur, d'un graphe sans Kk bornant tous les graphes sans Kk de C. Cette propriété avait été conjecturée et résolue dans un précédent article dans le cas particulier k=3. En particulier, nous prouvons (sans l'aide du théorème des quatre couleurs) l'existence d'un graphe H de nombre chromatique au plus 5 et de nombre de clique au plus 4, tel que tout graphe planaire soit homomorphique à H. Ce résultat est donc intermédiaire entre le théorème des quatre couleurs et le théorème des cinq couleurs. Le cas général semble lié à la conjecture de Hadwiger.
[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 ]
Nous présentons une version simplifiée de l'algorithme de test de planarité Gauche-Droite (basé sur un parcours en profondeur) qui est mis en œuvre dans Pigale et a étćonsidéré comme le plus rapide actuellement [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.]. Nous donnons une justification simple et complte de l'algorithme, basée sur une étude préliminaire des propriétés topologiques des arbres de DFS.
[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.
Nous montrons que l'ensemble des sommets d'un multigraphe G sans jumeaux a un plongement sur un ensemble de points P d'un espace Euclidien Rk, tel que le groupe d'automorphismes de G soit isomorphe au groupe d'isomtries de Rk prservant gloablement 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 ]
Nous donnons une condition ncessaire et suffisante pour qu'un graphe biparti connexe donn soit le graphe d'incidence d'une famille de contact de segments et de points. Nous dduisons que tout graphe 4-connexe 3-coloriable planaire est le graphe de contact d'une famille de segments et que tout graphe planaire 4-colori sans C4 induit utilisant 4 couleurs est le graphe d'intersection d'une famille de segments.
[A25] H. de Fraysseix and P. Ossona de Mendez. Barycentric systems and stretchability. Discrete Applied Mathematics, 155(9):1079–1095, 2007. [ DOI ]
À partir d'une résolution générale des systèmes barycentriques, nous proposons une généralisation du théorème de Tutte sur le tracé convexe des graphes planaires. Nous déduisons une caractérisation des couvertures de l'ensemble des arêtes d'un graphe planaires en chaînes non intersectantes rectifiables: un système de chaîne non intersectantes est rectifiable si et seulement si tout sous-système d'au moins deux chaînes possède au moins 3 sommets libres (sommets de la face extérieure du sous-graphe induit qui ne sont intérieurs à aucune des chaînes du sous système). Nous déduisons également qu'un système de contact de pseudo-segments est rectifiable si, et seulement si, il est extensible.
[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 ]
Nous tudions les dualits restreintes d'homomorphismes dans le contexte des classes d'expansion borne. Ceci reprsente une gnralisation des dualits restreintes mises en vidence prcdemment pour les graphes de degr born et pour les classes propres fermes par mineur. Ce rsultat est li au “coloration de distance” des graphes et une “approximation” de la conjecture de Hadwiger.
[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 ]
Les classes de graphes expansion borne sont une gnralisation des classes propres fermes par mineurs et des classes degr born. Ces classes sont dfinies partir d'un nouvel invariant, le greatest reduced average density (grad) de G de rank r, ∇r(G). Ces classes sont galement caractrises par l'existence de colorations induisant des graphes de faible tree-width ou de faible tree-depth. Ces rsultats amne diffrents nouveaux algorithmes en temps linaire, tel qu'un algorithme pour compter tous les sous-graphes isomorphes un graphe fix, ou un algorithme testant l'existence d'un sous-ensemble de sommets de taille borne a priori tel que le sous-graphe induit satisfasse une proprit arbitraire (mais fixe) exprime en logique du premier ordre. Nous montrons galement que pour tout p fix, le calcul de la distance entre deux points (jusqu' une distance de p) peut tre effectu en temps constant aprs un prtraitement effectu en temps linaire. Nous montrons galement, tendant ainsi divers rsultats prcdents, que les classes de graphe ayant une expansion sous-exponentielle ont des sparateurs de taille sous-linaire. Ce rsulat est optimal en gnral.
[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 ]
Nous introduisons les classes de graphes d'expansion borne en gnralisant les classes propres fermes par mineurs et les classes de degr born. Ces classes sont dfinies partir d'un nouvel invariant, le greatest reduced average density (grad) de G de rang r, ∇r(G). Pour ces classes, nous prouvons l'existence de diffrentes partitions, en particluier l'existence de partition induisant des graphes de faible tree-width et faible tree-depth. Nous gnralisons et simplifions diffrents resultats prcdents (obtenus pour les classes fermes par mineurs).
[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 ]
Nous caratrisons les notions d'arrangeabilit et d'admissibilit en termes de ∇1(G) (la conjecture de Burr – Erdős tant, elle, lie ∇0(G)). Nous en dduisons la linrit du nombre de Ramsey et du nombre chromatic de jeu pour de nouvelles classes de graphes.
[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 ]
[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.
[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 ]
[A33] J. Nešetřil and P. Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600–617, 2011. [ DOI ]
[A34] F. Fiorenzi, P. Ochem, P. Ossona de Mendez, and X. Zhu. Thue choosability of trees. Discrete Applied Mathematics, 159:2045–2049, 2011. [ DOI ]
[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 ]
[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 ]
[A38] H. de Fraysseix and P. Ossona de Mendez. Planarity and Trémaux trees. European Journal of Combinatorics, 33(3):279–293, 2012. [ DOI ]
[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 ]
[A41] J. Nešetřil and P. Ossona de Mendez. On low tree-depth decompositions. Graphs and Combinatorics, 31(6):1941–1963, 2015. [ DOI ]
[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 ]
[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.
[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 ]
[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 ]
[A47] J. Nešetřil and P. Ossona de Mendez. Existence of modeling limits for sequences of sparse structures. 2016. submitted.
[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 ]
[A49] J. Nešetřil and P. Ossona de Mendez. Towards a characterization of universal categories. Journal of Pure and Applied Algebra, 2016. [ DOI ]
[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.
[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 ]
[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.
[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 ]
[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.

[Haut de Page]

Actes de Conférence (avec comité de lecture)

[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 ]
Les orientations régulières, i.e. les orientations telles que presque tous les sommets aient le même degré entrant, relient de nombreuses propriétés combinatoires et topologiques, telles que l'arboricité, le page number et la planarité. Ces orientations constituent un outil de base dans la résolution de problèmes combinatoires dans lesquels des propriétés topologiques doivent être conservées. L'augmentation de graphes planaires est un exemple simple de tels problèmes.
[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 ]
La traversée d'un courbe simple auto-sécante du plan ayant des points de multiplicité au plus deux définit une suite à double occurences. C.F. Gauss a émis la conjoncture que ces séquences pouvaient être caractérisées par leurs propriétés d'entrelacement. Cette conjecture a été prouvée par P. Rosenstiehl en 1976. Nous donnons ici une preuve simple et auto-suffisante de cette caractérisation. Cette nouvelle preuve repose sur l'opération de “D-switch”.
[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.
Nous définissons le genre réduit d'un multigraphe comme étant le genre minimum d'un hypergraphe possédant les mêmes adjacences avec les mêmes multiplicités. Par une étude des hypergraphes plongés, nous obtenons de nouvelles bornes sur le nombre chromatique, le nombre de clique et l'arboricité des graphes simples de genre réduit donné. Nous présentons de nouveaux problèmes dérivés concernant la coloration et la représentation des graphes.
[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.
Nous montrons qu'un complexe simplicial abstrait S peut être réalisé géométriquement dans l'espace Euclidien de dimension (d-1), o d=P(S) est la dimension de Dushnik-Miller de l'ordre partiel d'inclusion des faces de 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.
Le tracé de structures combinatoires constitue un nouveau défi visant un meilleur contrle des données, aussi bien dans l'industrie que dans les affaires. En parlant de graphes, on entend généralement la notion de carte, le système de rotation des arêtes autour des sommets étant généralement spécifié par les structures de données. Le parcours constitue une étape cruciale des algorithmes de tracé. Le parcours en profondeur (DFS) a engendré dans le passé des algorithmes bien connus de test de planarité, de transformation de cartes et de tracé de graphe. Le parcours en largeur (BFS) qui a, par contre, été relativement négligé, apparaît comme l'outil approprié du codage des cartes. Nous explicitons ici une bijection entre les cartes pointées ayant m arêtes et les involutions connexes de {0,1,...,2m+1}.
[P6] P. Ossona de Mendez. Combinatorial hypermaps vs topic maps. In XML Europe 2001, 2001. [ .html ]
Les Topic Maps ont été introduites afin de permettre l'échange et la représentation d'informations relatives à la structure des ressources informationelles définies par des entité et des relations entres les entités. Les graphes et les hypergraphes ont été intdroduits en mathématiques discrètes pour des raisons similaires. Les besoins industriels liés aux Topic Maps concernent non seulement leur codage par une structure de données, mais aussi les requêtes complexes dont ils peuvent être l'objet, telles que parcours, analyse de structure, recherche de coupes minimales, etc. Le pardigme qui semble adaptés à ces problématiques semble reposé sur la strcture d'hypercarte introduite il y a quelques dizaines d'années. Cet article présente cet objet combinatoire, les structures de données associées et des considérations algorithmiques liées. Nous montrons que la théorie topologique des graphes constitue l'outil mathématique et algorithmique adapté à un traitement performant des Topic Maps.
[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.
Nous présentons un algorithme simple en temps linéaire de recherche d'une configuration de Kuratowski dans un graphe DFS coarbre-critique. Par soucis de clarté, les preuves des théorèmes utilisés sont esquissés. L'algortihme présenté constitue la deuxième moitié de l'algorithme de recherche en temps linéaire d'une configuration de Kuratowski dans un graphe non planaire mis en œuvre dans PIGALE (“Public Implementation of a Graph Algorithm Library and Editor”, librement accessible à l'adresse 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.
Nous donnons une caractérisation des graphes DFS-coarbre critique qui est centrale à l'algorithme en temps linéaire de recherche d'une configuration de Kuratowski mis en œuvre dans 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 ]
Les Topic Maps ont été développés afin de représenter des structures de mise en relations de sujets indépendamment des ressources les documentant, et afin de permettre une représentation standard et une interopérabilité de ces structures. La spécification ISO 13250 XTM a fournit une représentation syntaxique robuste dans le cadre XML, permettant le traitement et l'échange de Topic Maps. Néanmoins, les Topic Maps ont souffert de l'absence d'une véritable description formelle et d'un modèle conceptuel. Nous proposons un tel modèle, basé sur la notion d'hypergraphe et de connexité. Ce modèle aborde le problème critique de l'organisation des Topic Maps en niveaux sémantiques, et fournit une procédure de vérification de la consistance sémantique d'une Topic Map. Enfin, ce modèle semble suffisamment générique pour être utilisé comme fondation d'autres standards, tels que 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 ]
L'importance croissance de l'ducation distance (“e-learning”) a t un acclrateur l'mergence de services d'ducation bass sur Internet. Dans cet ge de l'information, des efforts importants et continus ont t apports au dveloppement de nouvelles technologies Web pour l'ducation, mettant en relation les ressources humaines et les attentes d'ducation. Cet article prsente les possibilits de Pliant en tant que logiciel adaptable facilitant le dveloppement de systmes de gestion d'ducation distance en preservant les attentes en termes d'ducation et de gnie logiciel. Il prsente les possibilits de Pliant en tant que nouvel outil logiciel et technologie Web ddis l'ducation distance.
[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 ]
Nous prouvons qu'un système de contact d'arcs de Jordan est rectifiable si, et seulement si, il est extensible en un système de pseudo lignes.
[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 ]
Nous donnons une condition ncessaire et suffisante pour qu'un graphe biparti connexe donn soit le graphe d'incidence d'une famille de segments et de points. Nous dduisons que tout graphe 4-connexe 3-coloriable planaire est le graphe de contact d'une famille de segments et que tout graphe planaire 4-colori sans C4 induit utilisant 4 couleurs est le graphe d'intersection d'une famille de 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 ]
Les classes d'expansion bornées généralisent les classes propres fermés par mineurs et les classes de degré borné. Pour tout classe C d'expansion bornée et pour tout entier p, il existe une constante N(C,p) telle que l'enesemble des sommets de tout graphe G∈C puisse être partionné en N(C,p) parties, ip quelconques d'entre elles induisant un sous-graphe de tree-width au plus (i-1) (en fait, de tree-depth au plus i, ce qui est sensiblement plus fort). De telles partitions sont centrales pour la résolution de certains problèmes liés à l'existence d'homomorphismes tels que les dualités restreintes d'homomorphismes. Nous explicitons un algorithme simple calculant de telles partitions et prouvons que si les graphes d'entrée sont restreints à une classe quelconque C d'expansion bornée, le temps d'exécution de l'algorithme est borné par une fonction linéaire de l'ordre du graphe (pour C et p fixés). De ce résultat, nous déduisons un algorithme en temps linéaire pour la recherche d'un sous-graphe isomorphe à un motif fixé au seins de graphes appartenant à une classe fixé d'expansion bornée. Plus généralement, si φ est un expression du premier ordre, la propriété `∃X: (|X|≤p) ∧(G[X]⊧φ)” peut être décidé en temps linéaire pour des graphes d'entrée restreints à une classe fixée d'expansion bornée.
[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 ]
Nous introduisons les classes de graphes d'ém expansion bornée comme généralisation des classes propres fermées par mineurs et des classes de degré borné. La définition de ces classes est basée sur un nouvel invariant, le greatest reduced average density (grad) de G de r, ∇r(G). Nous généralisons à ces classes des résultats prouvés pour les classes propres fermées par mineur et les classes de degré borné, tels que l'existence de partitions de faible largeur d'arbre, l'existence d'un algorithme en temps linéaire testant l'existence de sous-graphes isomorphes à un motif fixé, et l'existence de dualités restreintes d'homomorphismes.
[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 ]
De nombreux thormes de reprsentation s'tendent des graphes planaires aux hypergraphes planaires. Nanmoins, bien que la dmonstration de la reprsentabilit des graphes planaires par un systme de contacts de triangles conduise un algorithme simple en temps linaire, l'extension aux hypergraphes linaires planaires ne semble pas avoir de dmonstration simple. Nous en donnons une dmonstration ici, qui repose sur la caractrisation des hypergraphes de contact d'une famille de segments.
[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 ]
[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 ]
[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 ]
[Haut de Page]

Livres ou Chapitres de Livres

[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.
[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.
[Haut de Page]

Logiciels

[L1] H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. PICTEL. Industrial Software, 1984.
PICTEL est un logiciel de trac automatique de schma lctriques d'avions intgr au logiciel CATIA
[L2] H. de Fraysseix and P. Ossona de Mendez. Penelope. Industrial Software, 1990.
Penelope est un logiciel de conception et de simulation de tissu chanes et trames
[L3] P. Chicourrat, H. de Fraysseix, and P. Ossona de Mendez. A hierarchical diagram drawing software. Industrial Software, 1997.
Ce programme est un logiciel de trac automatique de diagrammes hierarchiques 4-faces
[L4] P. Ossona de Mendez and H. Tonneau. Pliant project. Free Software (GPL licence), 1999. [ http ]
Le projet Pliant consiste en la cration, sous licence GPL, d'un ensemble, cohrent et minimal, contenant les outils de base ncessaires la plupart des utilisateurs, outils concentrs dans un code source de faible taille l'aide d'un nouveau langage permettant de focaliser l'criture sur ce qui est pertinent, sans empcher le programmeur d'intervenir n'importe lequel des niveaux d'abstraction, d'imposer n'importe quelle exception aux rgles gnrales. Le projet Pliant est accessible 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 intègre une librairie d'algorithmes de traitements de graphe écrite en langage C++ et un éditeur de graphe basé sur les librairies Qt et OpenGL. Ce programme est particulièrement destiné à la recherche théorique sur les graphes topologiques. Pigale est disponible sous licence GPL et peut être téléchargé par FTP ou CVS depuis l'adresse: http://sourceforge.net/projects/pigale/
[L6] H. de Fraysseix, A. Joly, and P. Ossona de Mendez. Ariane. Software, 2003.
Ariane est une logiciel de gestion bibliographique
[Haut de Page]

Autres

[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.
Le sujet de cette thèse est le concept d'orientation bipolaire d'un graphe 2-connexe, i.e. d'orientation acyclique possédant une seule source et un seul puits. L'étude débute par l'abstraction des orientations bipolaires dans le cadre des matroïdes orientés réguliers; une telle abstraction est particulièrement appropriée à l'étude des propriétés d'effacement, de contraction et d' extension. Le codage original d'une orientation bipolaire quelconque par un graphe parfait conduit à une nouvelle caractérisation des matroïdes graphiques. La planarité d'un graphe est alors caractérisée en terme de dimension de l'ordre partiel d'arêtes induit par une orientation bipolaire. Dans le cas graphique, il est établi que deux orientations bipolaires quelconques d'un graphe 3-connexe sont connectées par une séquence d'orientations bipolaires obtenues à chaque étape en inversant l'orientation d'exactement une arête. Il est montré que dans le cas des graphes planaires, l'ensemble des orientations bipolaires est organisé en treillis distributif. La même structure est également mise en évidence sur l'ensemble des décompositions d'un graphe maximal planaire en trois arbres de Schnyder. Dans le dernier chapitre sont prouvés deux théorèmes de représentation: tout graphe planaire peut être représenté par une famille de triangles en contact; tout graphe biparti planaire peut être représenté par une famille de segments horizontaux et verticaux en contact.
[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.
L'orientation des langages de programmation semblent suivre deux orientations principales. La première correspond à la tentative des grandes compagnies d'acquérir de plus en plus d'emprise sur les utilisateurs finaux, tout en limitant leur propre responsabilité dans une sorte de “démocratie” sous tutelle. La seconde est une quête d'indépendance des utilisateurs qui s'exprime, notamment, au sein du mouvement “logiciel libre”. Alors que la première tendance mène à une sévère limitation des possibilités offertes aux programmeurs et à une uniformisation des logiciels “personnels” restreints à des “macros-logiciels”, le besoin qu'a la seconde d'une cohérence interne pourrait amener à introduire un nouveau type de système d'exploitation responsable d'une compilation indépendante du langage, que nous appelons système d'exploitation de langages, permettant un nouveau type d'intégration: l'intégration au niveau du langage.
[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 ]
[Haut de Page]

Actes de Conférence (sans comité de lecture)

[Haut de Page]

Prépublications ArXiv

[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.
[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.
[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.
[Haut de Page]

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.
Nous tudions les dualits restreintes d'homomorphismes dans le contexte des classes d'expansion borne. Ceci reprsente une gnralisation des dualits restreintes mises en vidence prcdemment pour les graphes de degr born et pour les classes propres fermes par mineur. Ce rsultat est li au “coloration de distance” des graphes et une “approximation” de la conjecture de Hadwiger.
[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.
Les classes de graphes expansion borne sont une gnralisation des classes propres fermes par mineurs et des classes degr born. Ces classes sont dfinies partir d'un nouvel invariant, le greatest reduced average density (grad) de G de rank r, ∇r(G). Ces classes sont galement caractrises par l'existence de colorations induisant des graphes de faible tree-width ou de faible tree-depth. Ces rsultats amne diffrents nouveaux algorithmes en temps linaire, tel qu'un algorithme pour compter tous les sous-graphes isomorphes un graphe fix, ou un algorithme testant l'existence d'un sous-ensemble de sommets de taille borne a priori tel que le sous-graphe induit satisfasse une proprit arbitraire (mais fixe) exprime en logique du premier ordre. Nous montrons galement que pour tout p fix, le calcul de la distance entre deux points (jusqu' une distance de p) peut tre effectu en temps constant aprs un prtraitement effectu en temps linaire. Nous montrons galement, tendant ainsi divers rsultats prcdents, que les classes de graphe ayant une expansion sous-exponentielle ont des sparateurs de taille sous-linaire. Ce rsulat est optimal en gnral.
[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.
Nous introduisons les classes de graphes d'expansion borne en gnralisant les classes propres fermes par mineurs et les classes de degr born. Ces classes sont dfinies partir d'un nouvel invariant, le greatest reduced average density (grad) de G de rang r, ∇r(G). Pour ces classes, nous prouvons l'existence de diffrentes partitions, en particluier l'existence de partition induisant des graphes de faible tree-width et faible tree-depth. Nous gnralisons et simplifions diffrents resultats prcdents (obtenus pour les classes fermes par mineurs).
[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.
[Haut de Page]

Rapports ALCOM

[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.
[Haut de Page]

Séries du CAMS

[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.
Intermédiaire entre textes et dessins, les diagrammes constitutent un paradigme naturel de l'interface homme-machine. Ainsi, les diagrammes hierarchiques sont un outil usuel en ingénierie pour la documentation de systèmes complexes. Alors que la documentation produite à la main est restreinte à des vues particulières du système, un générateur automatique de tracé de diagrammes permet d'appréhender les sous-systèmes fonctionnels définis à l'aide de requêtes.
[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 ]
Un lien est établi entre les orbites d'un groupe de permutation bigénéré et les composantes d'une permutation p sur un intervalle de N, les composantes correspondant aux sous intervalles fixés par p. Des bijections sont établies entre les familles combinatoires dont l'équicardinalité était considérée comme mystérieuse dans la littérature. Nous en déduisons un codage des cartes et des hypercartes.
[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.
En utilisant un résultat précédent de représentation des graphes planaires, nous prouvons le problème de la 3-colorabilité est NP-complet pour les graphes de contact de segments, même si les points de contacts ne peuvent appartenir qu'à au plus deux segments, si les segments n'utilisent que 4 directions et si la représentation est donnée.
[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.
[Haut de Page]

Résumés dans des actes de conférence

[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.
[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 ]
Nous introduisons les classes de graphes expansion borne comme une gnralisation, la fois, des classes propres fermes par mineurs, et des classes de graphes degr born. Ces classes sont dfinies partir d'un nouvel invariant, le grad de G de rank r, ∇r(G). Nous gnralisons ces classes certains rsultats dmontrs pours les classes propres fermes par mineurs et pour les graphes de degr born, tels que l'existence de coloration induisant des sous-graphes de faible largeur d'arbre ou l'existence de dualits d'homomorphisme.
[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: ]
Les classes d'expansion borne sont une gnralisation la fois des classes propres fermes par mineurs et des classes de degr born. Ces classes sont bases sur un nouvel invariant; le “greatest reduced average density” (grad) de rang r de G, ∇r(G). Ces classes sont galement caractrises par l'existence de partitions de faible tree-width. Ces rsultats mnent de nombreux algorithmes en temps linaire, tel qu'un algorithme permettant de dnombrer les sous graphes isomorphes un graphe fix ou un algorithme testant l'existence d'un sous graphe induit de taille borne a priori satisfaisant une proprit fixe du premier ordre. Pour tout entier p fix, le calcul de la distance entre deux sommets (jusqu' la distance p) peut tre effectu en temps constant par requte aprs un prtraitement effectu en temps linaire. De plus, les classes d'expansion borne par une fonction sous-exponentielle possdent galement des sparateurs de tailles sous-linaires.
[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 ]
[Haut de Page]

En préparation