Accéder directement au contenu

Nicolas Trotignon

76
Documents

Publications

Burling graphs revisited, part II: Structure

Pegah Pournajafi , Nicolas Trotignon
European Journal of Combinatorics, 2024, 116, pp.103849. ⟨10.1016/j.ejc.2023.103849.⟩
Article dans une revue hal-04253853v1

A class of graphs with large rankwidth

Chính Hoàng , Nicolas Trotignon
Discrete Mathematics, 2024, 347 (1), pp.113699
Article dans une revue hal-04253810v1

Burling graphs revisited, part III: Applications to χ -boundedness

Pegah Pournajafi , Nicolas Trotignon
European Journal of Combinatorics, 2024, 116, pp.103850. ⟨10.1016/j.ejc.2023.103850⟩
Article dans une revue hal-04253858v1

Burling graphs revisited, part I: New characterizations

Pegah Pournajafi , Nicolas Trotignon
European Journal of Combinatorics, 2023, 110, pp.103686. ⟨10.1016/j.ejc.2023.103686⟩
Article dans une revue hal-04253838v1

Graphs with polynomially many minimal separators

Tara Abrishami , Maria Chudnovsky , Cemil Dibek , Stéphan Thomassé , Nicolas Trotignon
Journal of Combinatorial Theory, Series B, 2022, 152, pp.248-280. ⟨10.1016/j.jctb.2021.10.003⟩
Article dans une revue hal-04046989v1
Image document

(Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth

Ni Luh Dewi Sintiari , Marcin Pilipczuk , Stéphan Thomassé , Nicolas Trotignon
Journal of Graph Theory, 2021, 97 (4), pp.624-641. ⟨10.1002/jgt.22675⟩
Article dans une revue hal-03255160v1
Image document

The (theta, wheel)-free graphs Part IV: Induced paths and cycles

Marko Radovanović , Nicolas Trotignon , Kristina Vušković
Journal of Combinatorial Theory, Series B, 2021, 146, pp.495-531. ⟨10.1016/j.jctb.2020.06.002⟩
Article dans une revue hal-03060185v1
Image document

On the tree-width of even-hole-free graphs

Pierre Aboulker , Isolde Adler , Eun Jung Kim , Ni Luh Dewi Sintiari , Nicolas Trotignon
European Journal of Combinatorics, 2021, 98, pp.103394. ⟨10.1016/j.ejc.2021.103394⟩
Article dans une revue hal-03367072v1
Image document

(Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels

Ni Luh Dewi Sintiari , Nicolas Trotignon
Journal of Graph Theory, 2021, ⟨10.1002/jgt.22666⟩
Article dans une revue hal-03255154v1
Image document

The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring

Marko Radovanović , Nicolas Trotignon , Kristina Vušković
Journal of Combinatorial Theory, Series B, 2020, 143, pp.185-218. ⟨10.1016/j.jctb.2019.07.003⟩
Article dans une revue hal-03060183v1

On the complexity of colouring antiprismatic graphs

Myriam Preissmann , Cléophée Robin , Nicolas Trotignon
Algorithmica, 2020, 83 (2), pp.589-612. ⟨10.1007/s00453-020-00767-7⟩
Article dans une revue hal-02392476v1
Image document

The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs

Emilie Diot , Marko Radovanović , Nicolas Trotignon , Kristina Vušković
Journal of Combinatorial Theory, Series B, 2020, 143, pp.123-147. ⟨10.1016/j.jctb.2017.12.004⟩
Article dans une revue hal-03060180v1
Image document

The (theta, wheel)-free graphs Part II: Structure theorem

Marko Radovanović , Nicolas Trotignon , Kristina Vušković
Journal of Combinatorial Theory, Series B, 2020, 143, pp.148-184. ⟨10.1016/j.jctb.2019.07.004⟩
Article dans une revue hal-03060182v1
Image document

Coloring square-free Berge graphs

Maria Chudnovsky , Irene Lo , Frédéric Maffray , Nicolas Trotignon , Kristina Vušković
Journal of Combinatorial Theory, Series B, 2019, 135, pp.96-128. ⟨10.1016/j.jctb.2018.07.010⟩
Article dans une revue hal-01993462v1
Image document

Triangle‐free graphs that do not contain an induced subdivision of K 4 are 3‐colorable

Maria Chudnovsky , Chun‐hung Liu , Oliver Schaudt , Sophie Spirkl , Nicolas Trotignon
Journal of Graph Theory, 2018
Article dans une revue hal-01993783v1

Stable Sets in {ISK4,wheel}-Free Graphs

Martin Milanič , Irena Penev , Nicolas Trotignon
Algorithmica, 2018, 80 (2), pp.415 - 447. ⟨10.1007/s00453-016-0255-3⟩
Article dans une revue hal-01904093v1

χ-bounds, operations, and chords

Nicolas Trotignon , Lan Anh Pham
Journal of Graph Theory, 2018, 88 (2), pp.312 - 336. ⟨10.1002/jgt.22214⟩
Article dans une revue hal-01904081v1
Image document

Colouring graphs with constraints on connectivity

Pierre Aboulker , Nick Brettell , Frédéric Havet , Dániel Marx , Nicolas Trotignon
Journal of Graph Theory, 2017, 85 (4), pp.814-838. ⟨10.1002/jgt.22109⟩
Article dans une revue hal-01570035v1

On rank-width of even-hole-free graphs

Isolde Adler , Ngoc Khang Le , Haiko Müller , Marko Radovanovic , Nicolas Trotignon
Discrete Mathematics and Theoretical Computer Science, 2017, 19 (1)
Article dans une revue hal-01719181v1

Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs

Martin Milanič , Nicolas Trotignon
Journal of Graph Theory, 2017, 84 (3), pp.536 - 551. ⟨10.1002/jgt.22040⟩
Article dans une revue hal-01391694v1

On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph

Nicolas Trotignon , Kristina Vušković
Journal of Graph Theory, 2017, 84 (3), pp.233 - 248. ⟨10.1002/jgt.22023⟩
Article dans une revue hal-01482299v1

A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs

Stéphan Thomassé , Nicolas Trotignon , Kristina Vušković
Algorithmica, 2017, 77 (3), pp.619 - 641. ⟨10.1007/s00453-015-0083-x⟩
Article dans une revue hal-01482301v1

Isolating Highly Connected Induced Subgraphs

Irena Penev , Stéphan Thomassé , Nicolas Trotignon
SIAM Journal on Discrete Mathematics, 2016, 30, pp.592-619. ⟨10.1137/140981939⟩
Article dans une revue hal-01324067v1

Perfect graphs of arbitrarily large clique-chromatic number

Pierre Charbit , Irena Penev , Stéphan Thomassé , Nicolas Trotignon
Journal of Combinatorial Theory, Series B, 2016, 116, pp.456-464. ⟨10.1016/j.jctb.2015.09.008⟩
Article dans une revue hal-01324052v1

Using SPQR-trees to speed up algorithms based on 2-cutset decompositions

C.M.H. de Figueiredo , H.B. de Macêdo Filho , Z. Li , R.C.S. Machado , N. Trotignon
Electronic Notes in Discrete Mathematics, 2015, 50, pp.169-174
Article dans une revue hal-01995140v1

Vertex elimination orderings for hereditary graph classes

Pierre Aboulker , Pierre Charbit , Nicolas Trotignon , Kristina Vušković
Discrete Mathematics, 2015, 338 (5), ⟨10.1016/j.disc.2014.12.014⟩
Article dans une revue hal-01230783v1

Coloring perfect graphs with no balanced skew-partitions

Maria Chudnovsky , Nicolas Trotignon , Théophile Trunck , Kristina Vušković
Journal of Combinatorial Theory, Series B, 2015, 115, pp.26-65. ⟨10.1016/j.jctb.2015.04.007⟩
Article dans une revue hal-01222922v1

Wheel-free planar graphs

Pierre Aboulker , Maria Chudnovsky , Paul Seymour , Nicolas Trotignon
European Journal of Combinatorics, 2015, 49, ⟨10.1016/j.ejc.2015.02.027⟩
Article dans une revue hal-01230782v1

Detecting wheels

Emilie Diot , Sébastien Tavenas , Nicolas Trotignon
Applicable Analysis and Discrete Mathematics, 2014, 8 (1), ⟨10.2298/AADM131128023D⟩
Article dans une revue hal-01230785v1

Linear Balanceable and Subcubic Balanceable Graphs*

Pierre Aboulker , Marko Radovanović , Nicolas Trotignon , Théophile Trunck , Kristina Vušković
Journal of Graph Theory, 2014, 75 (2), pp.150 - 166. ⟨10.1002/jgt.21728⟩
Article dans une revue hal-01719196v1

Complexity of colouring problems restricted to unichord-free and { square,unichord }-free graphs

Raphael C.S. Machado , Celina M.H. de Figueiredo , Nicolas Trotignon
Discrete Applied Mathematics, 2014, 164, ⟨10.1016/j.dam.2012.02.016⟩
Article dans une revue hal-01230809v1

Complements of not so perfect graphs

András Sebő , Zhentao Li , Raphael Machado , Stéphan Thomassé , Nicolas Trotignon
European Journal of Combinatorics, 2013, 4 (3), pp.299 - 310
Article dans une revue hal-00909511v1

Complements of nearly perfect graphs

Andras Gyarfas , Zhentao Li , Raphael Machado , András Sebő , Stéphan Thomassé
The Electronic Journal of Combinatorics, 2013, 4 (3), pp.299 - 310. ⟨10.4310/JOC.2013.v4.n3.a2⟩
Article dans une revue hal-01592744v1

Excluding induced subdivisions of the bull and related graphs.

Maria Chudnovsky , Irena Penev , Alexander Scott , Nicolas Trotignon
Journal of Graph Theory, 2012, 71 (1), pp.49-68. ⟨10.1002/jgt.20631⟩
Article dans une revue ensl-00800048v1

Detecting 2-joins faster

Charbit Pierre , Michel Habib , Trotignon Nicolas , Vuskovic Kristina
Journal of Discrete Algorithms, 2012, 17, pp.60-66
Article dans une revue ensl-00800019v1

Graphs that do not contain a cycle with a node that has at least two neighbors on it.

Pierre Aboulker , Marko Radovanovic , Nicolas Trotignon , Kristina Vuskovic
SIAM Journal on Discrete Mathematics, 2012, 26 (4), pp.1510-1531
Article dans une revue ensl-00800037v1

The chromatic gap and its extremes

Andras Gyarfas , András Sebő , Nicolas Trotignon
Journal of Combinatorial Theory, Series B, 2012, 102 (5), pp.1155-1178. ⟨10.1016/j.jctb.2012.06.001⟩
Article dans une revue ensl-00800043v1

Combinatorial optimization with 2-joins.

Nicolas Trotignon , Vuskovic Kristina
Journal of Combinatorial Theory, Series B, 2012, 102, pp.153-185. ⟨10.1016/j.jctb.2011.06.002⟩
Article dans une revue hal-00800197v1

On graphs with no induced subdivision of K4

Benjamin Lévêque , Frédéric Maffray , Nicolas Trotignon
Journal of Combinatorial Theory, Series B, 2012, 102, pp.924-947. ⟨10.1016/j.jctb.2012.04.005⟩
Article dans une revue lirmm-00736503v1
Image document

Finding an induced subdivision of a digraph.

Jørgen Bang-Jensen , Frédéric Havet , Nicolas Trotignon
Theoretical Computer Science, 2012, 443, pp.10--24
Article dans une revue hal-00749187v1
Image document

Claw-freeness, $3$-homogeneous subsets of a graph and a reconstruction problem

Maurice Pouzet , Hamza Si Kaddour , Nicolas Trotignon
Contributions to Discrete Mathematics, 2011, 6, pp.92-103
Article dans une revue hal-00839758v1

A structure theorem for graphs with no cycle with a unique chord and its consequences

Nicolas Trotignon , Kristina Vuskovic
Journal of Graph Theory, 2010, 63 (1), pp.31-67
Article dans une revue hal-00536450v1

The k-in-a-tree problem for graphs of girth at least k

Nicolas Trotignon , Wei Liu
Discrete Applied Mathematics, 2010, 158, pp.1644-1649
Article dans une revue hal-00536454v1

Detecting induced subgraphs

Benjamin Lévêque , David Y. Lin , Frédéric Maffray , Nicolas Trotignon
Discrete Applied Mathematics, 2009, 157 (17), pp.3540-3551. ⟨10.1016/j.dam.2009.02.015⟩
Article dans une revue hal-00432782v1

The four-in-a-tree problem for triangle-free graphs

Nicolas Trotignon , Christophe Picouleau , Nicolas Derhy
Graphs and Combinatorics, 2009, 25, pp.489-502
Article dans une revue hal-00536448v1
Image document

Coloring Artemis graphs

Benjamin Lévêque , Frédéric Maffray , Bruce Reed , Nicolas Trotignon
Theoretical Computer Science, 2009, 410, pp.2234-2240. ⟨10.1016/j.tcs.2009.02.012⟩
Article dans une revue hal-00004741v1

Algorithms for square-3PC(*,*)-free Berge graphs

Frédéric Maffray , Nicolas Trotignon , Kristina Vuskovic
SIAM Journal on Discrete Mathematics, 2008, 22 (1), pp.51-71. ⟨10.1137/050628520⟩
Article dans une revue hal-00258343v1

Decomposing Berge graphs and detecting balanced skew partitions

Nicolas Trotignon
Journal of Combinatorial Theory, Series B, 2008, 98 (1), pp.173-225. ⟨10.1016/j.jctb.2007.07.004⟩
Article dans une revue hal-00186951v1

A class of perfectly contractile graphs

Frédéric Maffray , Nicolas Trotignon
Journal of Combinatorial Theory, Series B, 2006, 96 (1), pp.1-19. ⟨10.1016/j.jctb.2005.06.011⟩
Article dans une revue hal-00166912v1

Algorithms for perfectly contractile graphs

Frédéric Maffray , Nicolas Trotignon
SIAM Journal on Discrete Mathematics, 2005, 19 (3), pp.553-574. ⟨10.1137/S0895480104442522⟩
Article dans une revue hal-00166911v1

Algorithms for perfectly contractile graphs

Frédéric Maffray , Nicolas Trotignon
SIAM Journal on Discrete Mathematics, 2005, 19 (3), pp.553-574
Article dans une revue hal-00363765v1

Ramsey-type results on singletons, co-singletons and montone sequences in large collections of sets

Nicolas Trotignon , Sylvain Gravier , Frédéric Maffray , Jérôme Renault
European Journal of Combinatorics, 2004, 25 (5), pp.719-734
Article dans une revue hal-00160012v1

A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs

Stéphan Thomassé , Nicolas Trotignon , Kristina Vušković
WG 2014, Jun 2014, Orleans, France. pp.408-419
Communication dans un congrès hal-01993372v1

Finding an induced subdivision of a digraph

Frédéric Havet , Jørgen Bang-Jensen , Nicolas Trotignon
VI Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2011), Apr 2011, Bariloche, Argentina. pp.09--14
Communication dans un congrès inria-00638464v1

Decomposing Berge graphs and detecting balanced skew partitions

Nicolas Trotignon
Graph Theory, organized by: Reinhard Diestel, Alexander Schrijver and Paul Seymour, Mar 2007, Oberwolfach, Germany
Communication dans un congrès hal-00265245v1

Detecting induced subgraphs

Nicolas Trotignon , Benjamin Lévêque , David Y. Lin , Frédéric Maffray
EUROCOMB'07, 2007, Seville, Spain. pp.207--211
Communication dans un congrès hal-00265499v1

On the structure of self-complementary graphs

Nicolas Trotignon
ICGT'05, 2005, Hyères, France. pp.79-82
Communication dans un congrès hal-00265500v1

Algorithms for 3PC- free Berge graphs

Nicolas Trotignon , Frédéric Maffray , Kristina Vuskovic
ICGT'05, 2005, Hyères, France. pp.73-77
Communication dans un congrès hal-00265501v1

Odd pair of cliques

Nicolas Trotignon , Frédéric Maffray , Michel Burlet
Graph Theory 2004, a Conference in Memory of Claude Berge, 2004, Paris, France. pp.85-95
Communication dans un congrès hal-00166915v1

LexBFS, Structure, and Algorithms

Nicolas Trotignon
Encyclopedia of Algorithms, Springer New York, pp.1103-1107, 2016
Chapitre d'ouvrage hal-01995745v1
Image document

Graphes parfaits : structure et algorithmes

Nicolas Trotignon
Autre [cs.OH]. Université Joseph-Fourier - Grenoble I, 2004. Français. ⟨NNT : ⟩
Thèse tel-00008558v1