# Publications

The publications related to the ANR project EGOS are listed below.

## Journals

**2013**

- V. Pilaud, C. Stump.
**EL-labelings and canonical spanning trees for subword complexes**,*Discrete Geometry and Optimization*, Fields Institute Communications Series, Springer, pp. 213-248, 2013. - G. Chapuy, V. Feray, E. Fusy.
**A simple model of trees for unicellular maps**,*Journal of Combinatorial Theory, Ser. A*, vol. 120(8), pp. 2064-2092, 2013. - D. Goncalves, A. Parreau, and A. Pinlou.
**Locally identifying coloring in bounded expansion classes of graphs**,*Discrete Applied Mathematics*, vol. 161(18), pp. 2946-2951, 2013.

**2014**

- M. Bonamy, B. Lévêque, A. Pinlou.
**List coloring the square of sparse graphs with large degree**,*European Journal of Combinatorics*, vol. 41, pp. 128-137, 2014. - J. Bouttier, É. Fusy, E. Guitter.
**On the two-point function of general planar maps and hypermaps**,*Annales de l’institut Henri Poincaré D*, vol. 1(3), pp. 265-306, 2014. - G. Collet, É. Fusy.
**A simple formula for the series of constellations and quasi-constellations with boundaries**,*Electr. J. Comb.*, vol. 21(2), P2.9, 2014. - É. Fusy, E. Guitter.
**The three-point function of general planar maps**.*J. Stat. Mech.*, P09012, 2014. - V. Pilaud, J. Rué.
**Analytic combinatorics of chord and hyperchord diagrams with k crossings**,*Advances in Applied Mathematics*, vol. 57, pp. 60-100, 2014. - D. Gonçalves, B. Léveque.
**Toroidal maps : Schnyder woods, orthogonal surfaces and straight-line representations**,*Discrete & Computational Geometry*, vol. 51(1), pp. 67-131, 2014. - M. Bonamy, B. Lévêque, A. Pinlou.
**2-distance coloring of sparse graphs**,*Journal of Graph Theory*, vol. 77, 190–218, 2014. - M. Bonamy, N. Bousquet,
**Brooks’ theorem on powers of graphs**,*Discrete Mathematics*, vol. 325, pp. 12–16, 2014. - M. Bonamy, B. Lévêque, A. Pinlou.
**Graphs with maximum degree \Delta\geq 17 and maximum average degree less than 3 are list 2-distance (\Delta+2)-colorable**,*Discrete Mathematics*, vol. 317, pp. 19-32, 2014. - J. Bokowski, V. Pilaud.
**Enumerating topological (n_k)-configurations**,*Computational Geometry: Theory and Applications*, vol. 47(2), pp. 175-186, 2014. - M. Albenque, É. Fusy, D. Poulalhon.
**On symmetric quadrangulations and triangulations**.*Eur. J. Comb.*, vol. 35, pp. 13-31, 2014.

**2015**

- G. Chapuy, É. Fusy, O. Giménez, M. Noy.
**On the Diameter of Random Planar Graphs**.*Combinatorics, Probability & Computing*, vol. 24(1), pp. 145-178, 2015. - É. Fusy, E. Guitter.
**The two-point function of bicolored planar maps**.*Annales de l'institut Henri Poincaré D*, vol. 2(4), pp. 335-412, 2015. - É. Fusy, A. Tanasa.
**Asymptotic expansion of the multi-orientable random tensor model**.*Electon. J. Combin.*, vol. 22(1), P52, 2015. - S. Bessy, D. Gonçalves, and J.-S. Sereni.
**Two-floor buildings need eight colors**,*Journal of Graph Algorithms and Applications*, vol. 19(1), pp. 1-9, 2015. - N. Bonichon, C. Gavoille, N. Hanusse, L. Perkovic.
**Tight Stretch Factors for L1- and L_inf-Delaunay Triangulations**,*Computational Geometry: Theory and Applications*, vol. 48, pp. 237-250, 2015. - V. Pilaud, C. Stump.
**Vertex barycenter of generalized associahedra**,*Proceedings of the American Mathematical Society*, vol. 143(6), pp. 2623-2636, 2015. - C. Ceballos, V. Pilaud.
**Denominator vectors and compatibility degrees in cluster algebras of finite type**,*Transactions of the American Mathematical Society*, vol. 367, pp. 1421-1439, 2015. - V. Pilaud, C. Stump.
**Brick polytopes of spherical subword complexes and generalized associahedra**,*Advances in Mathematics*, vol. 276, pp. 1-61, 2015. - J. Bokowski, V. Pilaud.
**On topological and geometric (19_4) configurations**,*European Journal of Combinatorics*, vol. 50, pp. 4-17, 2015. - T. Manneville, V. Pilaud.
**Graph properties of graph associahedra**,*Séminaire Lotharingien de Combinatoire*, B73d, 31 pp., 2015. - C. Ceballos, V. Pilaud.
**Cluster algebras of type D: pseudotriangulations approach**,*Electronic Journal of Combinatorics*, vol. 22(4), #P4.44, 21 pp., 2015. - N Bonichon, I Kanj, L Perković, G Xia.
**There are plane spanners of degree 4 and moderate stretch factor**, ''

Discrete & Computational Geometry'', 53 (3), 514-546, 2015

**2016**

- C. Ceballos, V. Pilaud.
**The diameter of type D associahedra and the non-leaving-face property**,*European Journal of Combinatorics*, vol. 51, pp. 109-124, 2016. - J. Bokowski, V. Pilaud.
**Quasi-configurations: building blocks for point-line configurations**,*ARS Mathematica Contemporanea*, vol. 10(1), pp. 99-112, 2016.

**To appear**

- L. Perkovic, N. Bonichon, L. Kanj and G. Xia.
**There are Plane Spanners of Maximum Degree 4**, to appear in*Discrete & Computational Geometry*. - M. Montassier, P. Ochem.
**Near-colorings: non-colorable graphs and NP-completeness**, to appear in*Electron. J. Comb*. - C. Lange, V. Pilaud.
**Associahedra via spines**, to appear in*Combinatorica*. - M. Bonamy, B. Lévêque, A. Pinlou.
**Planar graphs with \Delta\geq 7 and no triangle adjacent to a C_4 are minimally edge- and total-choosable**, to appear in*Discrete Mathematics and Theoretical Computer Science*. arXiv - M. Bonamy.
**Planar graphs with Delta>=8 are (Delta+1)-edge-choosable**,*SIAM Journal on Discrete Mathematics*. arXiv - M. Bonamy, R. Kang.
**List colouring with a bounded palette**,*Journal of Graph Theory*. arXiv

**Submitted**

- S. Jendrol', M. Macekova, M. Montassier, R. Sotak.
**3-paths in graphs with bounded maximum average degree**. - S. Jendrol', M. Macekova, M. Montassier, and R. Sotak.
**Unavoidable 3-paths in planar graphs of given girth**. - K. Knauer, L.P. Montejano, J.L. Ramírez.
**How many circuits determine an oriented matroid?**. - M. Bonamy.
**Planar graphs with Delta>=8 are (Delta+1)-edge-choosable**. arXiv - B. Albar, D.Gonçalves.
**On triangles in K_r-minor free graphs.**. arXiv - V. Pilaud.
**Signed tree associahedra**. arXiv - P. Ochem, A. Pinlou, S. Sen.
**Homomorphisms of signed planar graphs**. arXiv - B. Albar.
**Coloration of**. arXiv`⚠ $K_7^-$`

-minor free graphs - O. Bernardi, E. Fusy.
**Unified bijections for planar hypermaps with general cycle-length constraints**. arXiv - O. Bernardi, E. Fusy.
**Bijections for maps with boundaries: Krikun's formula for triangulations, and a quadrangulation analogue**. arXiv - N. Cohen, D. Gonçalves, E. J. Kim, C. Paul, I. Sau, D. M. Thilikos, M. Weller.
**A Polynomial-time Algorithm for Outerplanar Diameter Improvement**. arXiv - M. Bonamy, N. Bousquet,
**Recoloring graphs via tree decompositions**. arXiv - V. Pilaud.
**Which nestohedra are removahedra ?**. arXiv - M. Bonamy, N. Bousquet,
**Reconfiguring Independent Sets in Cographs**. arXiv - D. Gonçalves, M. Montassier, A. Pinlou.
**Entropy compression method applied to graph colorings**. arXiv - M. Bonamy, N. Bousquet, S. Thomassé,
**The Erdos-Hajnal Conjecture for Long Holes and Anti-holes**. arXiv - M. Bonamy, P. Charbit, S. Thomassé,
**Graphs with large chromatic number induce 3k-cycles**. arXiv - M. Bonamy, J. Przybyło,
**On the neighbour sum distinguishing index of planar graphs**. arXiv - F. Dross, M. Montassier, A. Pinlou.
**Large induced forests in planar graphs with girth 4 or 5**. arXiv - M. Bonamy, L. Kowalik,
**A 13k-kernel for Planar Feedback Vertex Set via Region Decomposition**. arXiv - G. Chatel, V. Pilaud.
**Cambrian Hopf Algebras**. arXiv - B. Albar, D. Gonçalves, K. Knauer.
**Orienting triangulations**. arXiv - M. Bonamy, H. Hocquard, S. Kerdjoudj, A. Raspaud,
**Incidence coloring of graphs with high maximum average degree**. arXiv - B. Albar, D. Gonçalves, J. L. Ramírez Alfonsín.
**Detecting minors in matroids through triangles**. arXiv - Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Ljubomir Perkovic, André van Renssen,
**Upper and Lower Bounds for Competitive Online Routing on Delaunay Triangulations**. arXiv - D. Gonçalves, K. Knauer, B. Lévêque.
**Structure of Schnyder labelings on orientable surfaces**. arXiv - T. Manneville, V. Pilaud.
**Compatibility fans for graphical nested complexes**. arXiv - V. Pilaud.
**Brick polytopes, lattice quotients, and Hopf algebras**. arXiv - A. Dermenjian, C. Hohlweg, V. Pilaud.
**The facial weak order and its lattice quotients**. arXiv - F. Dross, M. Montassier, and A. Pinlou.
**Partitioning a triangle-free planar graph into a forest and a forest of bounded degree**, arXiv. - F. Dross, M. Montassier, and A. Pinlou.
**A lower bound on the order of the largest induced forest in planar graphs with high girth**, arXiv. - M. Bonamy, N. Bousquet.
**Recoloring graphs via tree decompositions**. arXiv - M. Bonamy, N. Bousquet.
**Reconfiguring Independent Sets in Cographs**. arXiv - M. Bonamy, J. Przybyło.
**On the neighbour sum distinguishing index of planar graphs**. arXiv - M. Bonamy, P. Charbit, S. Thomassé.
**Graphs with large chromatic number induce 3k-cycles**. arXiv - M. Bonamy, N. Bousquet, S. Thomassé.
**The Erdős-Hajnal conjecture for long holes and anti-holes**. arXiv - M. Bonamy, Ł. Kowalik,
**A 13k-kernel for Planar Feedback Vertex Set via Region Decomposition**. arXiv - M. Bonamy, H. Hocquard, S. Kerdjoudj, A. Raspaud.
**Incidence coloring of graphs with high maximum average degree**. arXiv - M. Bonamy, D. Cranston, L. Postle
**Planar Graphs of Girth at least Five are Square (Δ+2)-Choosable**. arXiv - M. Bonamy, Ł. Kowalik, M. Pilipczuk.
**A. Socała, Linear kernels for outbranching problems in sparse digraphs**. arXiv

## Conferences

**2013**

- C. Ceballos, V. Pilaud.
**Denominator vectors and compatibility degrees in cluster algebras of finite type**,*25th Intern. Conf. Formal Power Series and Algebraic Combinatorics*, pp. 85-96, 2013. - V. Pilaud, C. Stump.
**EL-labelings and canonical spanning trees for subword complexes**,*25th Intern. Conf. Formal Power Series and Algebraic Combinatorics*, pp. 611-622, 2013. - B. Albar, D. Gonçalves.
**Too many triangles**, in Proc. of*LAGOS 2013*, Electronic Notes in Discrete Mathematics, vol 44, pp 293-297, 2013. - L. Castelli Aleardi, O. Devillers, É. Fusy.
**Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-Line Drawings.**, in*Proc. of Graph Drawing 2012*, Lecture Notes in Computer Science Volume 7704, pp 376-387, 2013. - M. Bonamy.
**Planar graphs with Delta>=8 are (Delta+1)-edge-choosable**,*EuroComb 13*, CRM Series, vol. 16, pp 241-244, 2013. - M. Bonamy, N. Bousquet, H. Hocquard.
**Adjacent vertex-distinguishing edge coloring of graphs**,*EuroComb 13*, CRM Series, vol. 16, pp 313-318, 2013. - M. Bonamy, N. Bousquet.
**Recoloring bounded treewidth graphs**,*LAGOS'13*,*Elect. Notes Disc. Math.*vol. 44, pp 257–262, 2013.

**2014**

- L. Castelli Aleardi, É. Fusy, A. Kostrygin.
**Periodic planar straight-frame drawings with polynomial resolution**.*Proc. of 11th Latin American Theoretical INformatics Symposium (LATIN 2014)*, Springer LNCS, vol. 8392, pp. 168-179, 2014. - O. Bernardi, G. Collet, É. Fusy.
**A bijection for plane graphs and its applications**.*Proceedings of ANALCO'14*. pp. 52-61, 2014. - O. Bernardi, G. Collet, É. Fusy.
**On the distance-profile of random rooted plane graphs**.*Proceedings of AofA'14*. pp. 37-48, 2014. - V. Pilaud, J. Rué.
**Analytic combinatorics of chord and hyperchord diagrams with k crossings**.*25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms*, 12 pp., 2014. - V. Pilaud.
**Signed tree associahedra**.*26th Intern. Conf. Formal Power Series and Algebraic Combinatorics*, pp. 309-320, 2014. - L. Perkovic, N. Bonichon, L. Kanj and G. Xia.
**There are Plane Spanners of Maximum Degree 4**,*SoCG*,pp. 20-29, 2014. - S. Felsner, K. Knauer, G.B. Mertzios, T. Ueckerdt.
**Intersection Graphs of L-Shapes and Segments in the Plane**,*MFCS 14*,*Lecture Notes in Computer Science*, vol 8635, pp. 299-310, 2014. - M. Bonamy, L. Kowalik.
**A 14k-kernel for Planar Feedback Vertex Set via Region Decomposition**,*IPEC 2014*, pp. 97-109.

**2015**

- B. Albar, D. Gonçalves, K. Knauer.
**Orienting triangulations**.*Proceedings of EuroCG*, 2015. - L. Castelli Aleardi, A. Nolin, M. Ovsjanikov.
**Efficient and practical tree preconditioning for solving Laplacian systems**,*Proc. of 14th Int. Symp. on Experimental Algorithms (SEA'15)*, Springer LNCS, vol. 9125, p. 219-231, 2015. - N. Cohen, D. Gonçalves, E. J. Kim, C. Paul, I. Sau, D. M. Thilikos, M. Weller.
**A Polynomial-time Algorithm for Outerplanar Diameter Improvement**. Proceedings of the*10th International Computer Science Symposium in Russia*, 2015. - G. Chatel, V. Pilaud.
**The Cambrian Hopf Algebra**.*27th Intern. Conf. Formal Power Series and Algebraic Combinatorics*, DMTCS Proc., pp. 61-72, 2015. - C. Ceballos, T. Manneville, V. Pilaud, L. Pournin.
**Diameters and geodesic properties of generalizations of the associahedron**.*27th Intern. Conf. Formal Power Series and Algebraic Combinatorics*, DMTCS Proc., pp. 345-356, 2015. - N Bonichon, P Bose, JL De Carufel, L Perković, A Van Renssen,
**Upper and Lower Bounds for Competitive Online Routing on Delaunay Triangulations**,*ESA*, pp. 203-214, 2015. - D Auber, N Bonichon, P Dorbec, C Pennarun.
**Rook-drawing for plane graphs**,*Graph Drawing and Network Visualization*, pp. 180-191, 2015. - F. Dross, M. Montassier, and A. Pinlou.
**Partitioning a triangle-free planar graph into a forest and a forest of bounded degree**,*European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015*, pp. 269-275, 2015.

**2016**

- A. Dermenjian, C. Hohlweg, V. Pilaud.
**The facial weak order in finite Coxeter groups**.*28th Intern. Conf. Formal Power Series and Algebraic Combinatorics*, DMTCS Proc., 2016. - T. Manneville, V. Pilaud.
**Compatibility fans realizing graphical nested complexes**.*28th Intern. Conf. Formal Power Series and Algebraic Combinatorics*, DMTCS Proc., 2016. - V. Pilaud.
**Brick polytopes, lattices and Hopf algebras**.*28th Intern. Conf. Formal Power Series and Algebraic Combinatorics*, DMTCS Proc., 2016.