Skip to Main content
Number of documents

70

Nicolas Trotignon (CNRS researcher)


Journal articles46 documents

  • Marko Radovanović, Nicolas Trotignon, Kristina Vušković. The (theta, wheel)-free graphs Part IV: Induced paths and cycles. Journal of Combinatorial Theory, Series B, Elsevier, 2021, 146, pp.495-531. ⟨10.1016/j.jctb.2020.06.002⟩. ⟨hal-03060185⟩
  • Ni Luh Dewi Sintiari, Marcin Pilipczuk, Stéphan Thomassé, Nicolas Trotignon. (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth. Journal of Graph Theory, Wiley, 2021, 97 (4), pp.624-641. ⟨10.1002/jgt.22675⟩. ⟨hal-03255160⟩
  • Ni Luh Dewi Sintiari, Nicolas Trotignon. (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels. Journal of Graph Theory, Wiley, 2021, ⟨10.1002/jgt.22666⟩. ⟨hal-03255154⟩
  • Emilie Diot, Marko Radovanović, Nicolas Trotignon, Kristina Vušković. The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs. Journal of Combinatorial Theory, Series B, Elsevier, 2020, 143, pp.123-147. ⟨10.1016/j.jctb.2017.12.004⟩. ⟨hal-03060180⟩
  • Marko Radovanović, Nicolas Trotignon, Kristina Vušković. The (theta, wheel)-free graphs Part II: Structure theorem. Journal of Combinatorial Theory, Series B, Elsevier, 2020, 143, pp.148-184. ⟨10.1016/j.jctb.2019.07.004⟩. ⟨hal-03060182⟩
  • Marko Radovanović, Nicolas Trotignon, Kristina Vušković. The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring. Journal of Combinatorial Theory, Series B, Elsevier, 2020, 143, pp.185-218. ⟨10.1016/j.jctb.2019.07.003⟩. ⟨hal-03060183⟩
  • Myriam Preissmann, Cléophée Robin, Nicolas Trotignon. On the complexity of colouring antiprismatic graphs. Algorithmica, Springer Verlag, 2020, 83 (2), pp.589-612. ⟨10.1007/s00453-020-00767-7⟩. ⟨hal-02392476⟩
  • Maria Chudnovsky, Irene Lo, Frédéric Maffray, Nicolas Trotignon, Kristina Vušković. Coloring square-free Berge graphs. Journal of Combinatorial Theory, Series B, Elsevier, 2019, 135, pp.96-128. ⟨10.1016/j.jctb.2018.07.010⟩. ⟨hal-01993462⟩
  • Nicolas Trotignon, Lan Anh Pham. χ-bounds, operations, and chords. Journal of Graph Theory, Wiley, 2018, 88 (2), pp.312 - 336. ⟨10.1002/jgt.22214⟩. ⟨hal-01904081⟩
  • Martin Milanič, Irena Penev, Nicolas Trotignon. Stable Sets in {ISK4,wheel}-Free Graphs. Algorithmica, Springer Verlag, 2018, 80 (2), pp.415 - 447. ⟨10.1007/s00453-016-0255-3⟩. ⟨hal-01904093⟩
  • Maria Chudnovsky, Chun‐hung Liu, Oliver Schaudt, Sophie Spirkl, Nicolas Trotignon, et al.. Triangle‐free graphs that do not contain an induced subdivision of K 4 are 3‐colorable. Journal of Graph Theory, Wiley, 2018. ⟨hal-01993783⟩
  • Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković. A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs. Algorithmica, Springer Verlag, 2017, 77 (3), pp.619 - 641. ⟨10.1007/s00453-015-0083-x⟩. ⟨hal-01482301⟩
  • Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanovic, Nicolas Trotignon, et al.. On rank-width of even-hole-free graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2017, 19 (1). ⟨hal-01719181⟩
  • Martin Milanič, Nicolas Trotignon. Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs. Journal of Graph Theory, Wiley, 2017, 84 (3), pp.536 - 551. ⟨10.1002/jgt.22040⟩. ⟨hal-01391694⟩
  • Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon. Colouring graphs with constraints on connectivity. Journal of Graph Theory, Wiley, 2017, 85 (4), pp.814-838. ⟨10.1002/jgt.22109⟩. ⟨hal-01570035⟩
  • Nicolas Trotignon, Kristina Vušković. On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph. Journal of Graph Theory, Wiley, 2017, 84 (3), pp.233 - 248. ⟨10.1002/jgt.22023⟩. ⟨hal-01482299⟩
  • Pierre Charbit, Irena Penev, Stéphan Thomassé, Nicolas Trotignon. Perfect graphs of arbitrarily large clique-chromatic number. Journal of Combinatorial Theory, Series B, Elsevier, 2016, 116, pp.456-464. ⟨10.1016/j.jctb.2015.09.008⟩. ⟨hal-01324052⟩
  • Irena Penev, Stéphan Thomassé, Nicolas Trotignon. Isolating Highly Connected Induced Subgraphs. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30, pp.592-619. ⟨10.1137/140981939⟩. ⟨hal-01324067⟩
  • Pierre Aboulker, Pierre Charbit, Nicolas Trotignon, Kristina Vušković. Vertex elimination orderings for hereditary graph classes. Discrete Mathematics, Elsevier, 2015, 338 (5), ⟨10.1016/j.disc.2014.12.014⟩. ⟨hal-01230783⟩
  • Pierre Aboulker, Maria Chudnovsky, Paul Seymour, Nicolas Trotignon. Wheel-free planar graphs. European Journal of Combinatorics, Elsevier, 2015, 49, ⟨10.1016/j.ejc.2015.02.027⟩. ⟨hal-01230782⟩
  • Maria Chudnovsky, Nicolas Trotignon, Théophile Trunck, Kristina Vušković. Coloring perfect graphs with no balanced skew-partitions. Journal of Combinatorial Theory, Series B, Elsevier, 2015, 115, pp.26-65. ⟨10.1016/j.jctb.2015.04.007⟩. ⟨hal-01222922⟩
  • C.M.H. de Figueiredo, H.B. de Macêdo Filho, Z. Li, R.C.S. Machado, N. Trotignon. Using SPQR-trees to speed up algorithms based on 2-cutset decompositions. Electronic Notes in Discrete Mathematics, Elsevier, 2015, 50, pp.169-174. ⟨hal-01995140⟩
  • Raphael C.S. Machado, Celina M.H. de Figueiredo, Nicolas Trotignon. Complexity of colouring problems restricted to unichord-free and { square,unichord }-free graphs. Discrete Applied Mathematics, Elsevier, 2014, 164, ⟨10.1016/j.dam.2012.02.016⟩. ⟨hal-01230809⟩
  • Pierre Aboulker, Marko Radovanović, Nicolas Trotignon, Théophile Trunck, Kristina Vušković. Linear Balanceable and Subcubic Balanceable Graphs*. Journal of Graph Theory, Wiley, 2014, 75 (2), pp.150 - 166. ⟨10.1002/jgt.21728⟩. ⟨hal-01719196⟩
  • Emilie Diot, Sébastien Tavenas, Nicolas Trotignon. Detecting wheels. Applicable Analysis and Discrete Mathematics, Department of Applied Mathematics, University of Belgrade, 2014, 8 (1), ⟨10.2298/AADM131128023D⟩. ⟨hal-01230785⟩
  • Andras Gyarfas, Zhentao Li, Raphael Machado, András Sebő, Stéphan Thomassé, et al.. Complements of nearly perfect graphs. The Electronic Journal of Combinatorics, Open Journal Systems, 2013, 4 (3), pp.299 - 310. ⟨10.4310/JOC.2013.v4.n3.a2⟩. ⟨hal-01592744⟩
  • András Sebő, Zhentao Li, Raphael Machado, Stéphan Thomassé, Nicolas Trotignon. Complements of not so perfect graphs. European Journal of Combinatorics, Elsevier, 2013, 4 (3), pp.299 - 310. ⟨hal-00909511⟩
  • Pierre Aboulker, Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic. Graphs that do not contain a cycle with a node that has at least two neighbors on it.. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2012, 26 (4), pp.1510-1531. ⟨ensl-00800037⟩
  • Maria Chudnovsky, Irena Penev, Alexander Scott, Nicolas Trotignon. Excluding induced subdivisions of the bull and related graphs.. Journal of Graph Theory, Wiley, 2012, 71, pp.49-68. ⟨ensl-00800048⟩
  • Nicolas Trotignon, Vuskovic Kristina. Combinatorial optimization with 2-joins.. Journal of Combinatorial Theory, Series B, Elsevier, 2012, 102, pp.153-185. ⟨hal-00800197⟩
  • Charbit Pierre, Michel Habib, Trotignon Nicolas, Vuskovic Kristina. Detecting 2-joins faster. Journal of Discrete Algorithms, Elsevier, 2012, 17, pp.60-66. ⟨ensl-00800019⟩
  • Jørgen Bang-Jensen, Frédéric Havet, Nicolas Trotignon. Finding an induced subdivision of a digraph.. Theoretical Computer Science, Elsevier, 2012, 443, pp.10--24. ⟨hal-00749187⟩
  • Benjamin Lévêque, Frédéric Maffray, Nicolas Trotignon. On graphs with no induced subdivision of K4. Journal of Combinatorial Theory, Series B, Elsevier, 2012, 102, pp.924-947. ⟨10.1016/j.jctb.2012.04.005⟩. ⟨lirmm-00736503⟩
  • Andras Gyarfas, András Sebő, Nicolas Trotignon. The chromatic gap and its extremes. Journal of Combinatorial Theory, Series B, Elsevier, 2012, 102 (5), pp.1155-1178. ⟨ensl-00800043⟩
  • Maurice Pouzet, Hamza Si Kaddour, Nicolas Trotignon. Claw-freeness, $3$-homogeneous subsets of a graph and a reconstruction problem. Contributions to Discrete Mathematics, University of Calgary, 2011, 6, pp.92-103. ⟨hal-00839758⟩
  • Nicolas Trotignon, Kristina Vuskovic. A structure theorem for graphs with no cycle with a unique chord and its consequences. Journal of Graph Theory, Wiley, 2010, 63 (1), pp.31-67. ⟨hal-00536450⟩
  • Nicolas Trotignon, Wei Liu. The k-in-a-tree problem for graphs of girth at least k. Discrete Applied Mathematics, Elsevier, 2010, 158, pp.1644-1649. ⟨hal-00536454⟩
  • Nicolas Trotignon, Christophe Picouleau, Nicolas Derhy. The four-in-a-tree problem for triangle-free graphs. Graphs and Combinatorics, Springer Verlag, 2009, 25, pp.489-502. ⟨hal-00536448⟩
  • Benjamin Lévêque, David Y. Lin, Frédéric Maffray, Nicolas Trotignon. Detecting induced subgraphs. Discrete Applied Mathematics, Elsevier, 2009, 157 (17), pp.3540-3551. ⟨hal-00432782⟩
  • Benjamin Lévêque, Frédéric Maffray, Bruce Reed, Nicolas Trotignon. Coloring Artemis graphs. Theoretical Computer Science, Elsevier, 2009, 410, pp.2234-2240. ⟨10.1016/j.tcs.2009.02.012⟩. ⟨hal-00004741⟩
  • Frédéric Maffray, Nicolas Trotignon, Kristina Vuskovic. Algorithms for square-3PC(*,*)-free Berge graphs. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2008, 22 (1), pp.51-71. ⟨10.1137/050628520⟩. ⟨hal-00258343⟩
  • Nicolas Trotignon. Decomposing Berge graphs and detecting balanced skew partitions. Journal of Combinatorial Theory, Series B, Elsevier, 2008, 98 (1), pp.173-225. ⟨10.1016/j.jctb.2007.07.004⟩. ⟨hal-00186951⟩
  • Frédéric Maffray, Nicolas Trotignon. A class of perfectly contractile graphs. Journal of Combinatorial Theory, Series B, Elsevier, 2006, 96 (1), pp.1-19. ⟨10.1016/j.jctb.2005.06.011⟩. ⟨hal-00166912⟩
  • Frédéric Maffray, Nicolas Trotignon. Algorithms for perfectly contractile graphs. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2005, 19 (3), pp.553-574. ⟨hal-00363765⟩
  • Frédéric Maffray, Nicolas Trotignon. Algorithms for perfectly contractile graphs. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2005, 19 (3), pp.553-574. ⟨10.1137/S0895480104442522⟩. ⟨hal-00166911⟩
  • Nicolas Trotignon, Sylvain Gravier, Frédéric Maffray, Jérôme Renault. Ramsey-type results on singletons, co-singletons and montone sequences in large collections of sets. European Journal of Combinatorics, Elsevier, 2004, 25 (5), pp.719-734. ⟨hal-00160012⟩

Conference papers7 documents

  • Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković. A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs. WG 2014, Jun 2014, Orleans, France. pp.408-419. ⟨hal-01993372⟩
  • Frédéric Havet, Jørgen Bang-Jensen, Nicolas Trotignon. Finding an induced subdivision of a digraph. VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2011), Apr 2011, Bariloche, Argentina. pp.09--14. ⟨inria-00638464⟩
  • Nicolas Trotignon. Decomposing Berge graphs and detecting balanced skew partitions. Graph Theory, organized by: Reinhard Diestel, Alexander Schrijver and Paul Seymour, Mar 2007, Oberwolfach, Germany. ⟨hal-00265245⟩
  • Nicolas Trotignon, Benjamin Lévêque, David Y. Lin, Frédéric Maffray. Detecting induced subgraphs. EUROCOMB'07, 2007, Seville, Spain. pp.207--211. ⟨hal-00265499⟩
  • Nicolas Trotignon, Frédéric Maffray, Kristina Vuskovic. Algorithms for 3PC- free Berge graphs. ICGT'05, 2005, Hyères, France. pp.73-77. ⟨hal-00265501⟩
  • Nicolas Trotignon. On the structure of self-complementary graphs. ICGT'05, 2005, Hyères, France. pp.79-82. ⟨hal-00265500⟩
  • Nicolas Trotignon, Frédéric Maffray, Michel Burlet. Odd pair of cliques. Graph Theory 2004, a Conference in Memory of Claude Berge, 2004, Paris, France. pp.85-95. ⟨hal-00166915⟩

Book sections1 document

  • Nicolas Trotignon. LexBFS, Structure, and Algorithms. Encyclopedia of Algorithms, Springer New York, pp.1103-1107, 2016. ⟨hal-01995745⟩

Other publications8 documents

  • Nicolas Trotignon, Kristina Vuskovic. A structure theorem for graphs with no cycle with a unique chord and its consequences. 2008. ⟨halshs-00265957⟩
  • Nicolas Derhy, Christophe Picouleau, Nicolas Trotignon. The four-in-a-tree problem in triangle-free graphs. 2008. ⟨halshs-00270623⟩
  • Benjamin Lévêque, David Y. Lin, Frédéric Maffray, Nicolas Trotignon. Detecting induced subgraphs. 2007. ⟨halshs-00180953⟩
  • Benjamin Lévêque, Frédéric Maffray, Nicolas Trotignon. On graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. 2007. ⟨halshs-00180961⟩
  • Nicolas Trotignon. Decomposing Berge graphs and detecting balanced skew partitions. 2006. ⟨halshs-00115625⟩
  • Nicolas Trotignon. Decomposing Berge graphs. 2006. ⟨halshs-00082823⟩
  • Frédéric Maffray, Nicolas Trotignon, Kristina Vuskovic. Algorithms for square-3PC(.,.)-free Berge graphs. 2006. ⟨halshs-00130439⟩
  • Nicolas Trotignon. A new decomposition theorem for Berge graphs. 2005. ⟨halshs-00196448⟩

Preprints, Working Papers, ...5 documents

  • Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, Nicolas Trotignon. On the tree-width of even-hole-free graphs. 2021. ⟨hal-03107567⟩
  • Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković. Maximum independent sets in (pyramid, even hole)-free graphs. 2021. ⟨hal-02424059⟩
  • Louis Esperet, Nicolas Trotignon. Coloring graphs with no induced subdivision of $K_4^+$. 2021. ⟨hal-03092640⟩
  • Chính Hoàng, Nicolas Trotignon. A class of graphs with large rankwidth. 2020. ⟨hal-03029483⟩
  • Ni Luh Dewi Sintiari, Nicolas Trotignon. (Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 1 : Layered wheels. 2019. ⟨hal-02190126⟩

Reports2 documents

  • Pierre Aboulker, Frédéric Havet, Nicolas Trotignon. On wheel-free graphs. [Research Report] RR-7651, INRIA. 2011. ⟨inria-00602079⟩
  • Jørgen Bang-Jensen, Frédéric Havet, Nicolas Trotignon. Finding an induced subdivision of a digraph. [Research Report] RR-7430, INRIA. 2010. ⟨inria-00527518⟩

Theses1 document

  • Nicolas Trotignon. Graphes parfaits : structure et algorithmes. Autre [cs.OH]. Université Joseph-Fourier - Grenoble I, 2004. Français. ⟨tel-00008558⟩