On treewidth and maximum cliques.
( with Nicolas Trotignon),
manuscript
Unavoidable induced subgraphs in graphs with complete bipartite induced minors
( with Meike Hatzel, Tuukka Korhonen, Nicolas Trotignon, Sebastian Wiederrecht),
submitted for publication
Tree independence number I. (Even hole, diamond, pyramid)-free graphs ,
( with Tara Abrishami, Bogdan Alecu, Sepehr Hajebi, Sophie Spirkl and Kristina Vuskovic),
Journal of Graph Theory, 106 (2024), 924-943.
Tree independence number II. 3PC-free graphs. ,
( with Sepehr Hajebi, Daniel Lokshtanov and Sophie Spirkl),
submitted for publication
Tree independence number III. Thetas, prisms and stars. ,
( with Sepehr Hajebi and Nicolas Trotignon),
submitted for publication
Induced subgraphs and tree-decompositions
Induced subgraphs and tree-decompositions I. Even-hole-free graphs of bounded degree,
( with Tara Abrishami and Kristina Vuskovic)
Journal of Combinatorial Theory, Ser. B, 157 (2022), 144-175
Induced subgraphs and tree-decompositions II. Toward walls and their line graphs in graphs of bounded degree,
( with Tara Abrishami, Cemil Dibek, Sepehr Hajebi, Pawel Rzazewski, Sophie Spirkl and Kristina Vuskovic)
to appear in Journal of Combinatorial Theory, Ser. B
Induced subgraphs and tree-decompositions III.
Three-path-configurations and logarithmic tree-width,
( with Tara Abrishami, Sepehr Hajebi, and Sophie Spirkl)
Advances in Combinatorics (2022)
Induced subgraphs and tree-decompositions IV. (Even hole, diamond, pyramid)-free graphs.
( with Tara Abrishami, Sepehr Hajebi, and Sophie Spirkl)
Electronic J. of Combinatorics 30 (2023), P2.42
Induced subgraphs and tree-decompositions V. One neighbor in a hole.
( with Tara Abrishami, Bogdan Alecu, Sepehr Hajebi, Sophie Spirkl and Kristina Vuskovic)
Journal of Graph Theory, 105 (2024), 542-561
Induced subgraphs and tree-decompositions VI. Graphs with 2-cutsets.
( with Tara Abrishami, Sepehr Hajebi, and Sophie Spirkl)
Discrete Math, 348 (2025), 114195}
Induced subgraphs and tree-decompositions VII. Basic obstructions in H-free graphs.
( with Tara Abrishami, Bogdan Alecu, Sepehr Hajebi, and Sophie Spirkl)
Journal of Combinatorial Theory, Ser B, 164 (2024), 443-472
Induced subgraphs and tree-decompositions VIII. Excluding a forest in
(prism,theta)-free graphs.
( with Tara Abrishami, Bogdan Alecu, Sepehr Hajebi, and Sophie Spirkl)
to appear in Combinatorica
Induced subgraphs and tree-decompositions IX. Grid theorem for perforated graphs
( with Bogdan Alecu, Sepehr Hajebi, and Sophie Spirkl)
submitted for publication
Induced subgraphs and tree-decompositions X.
Towards logarithmic treewidth in even hole free graphs.
( with Tara Abrishami, Bogdan Alecu, Sepehr Hajebi, and Sophie Spirkl)
submitted for publication
Induced subgraphs and tree-decompositions XI.
Local structure in even-hole-free graphs of large tree-width.
( with Bogdan Alecu, Sepehr Hajebi, and Sophie Spirkl)
submitted for publication
Induced subgraphs and tree-decompositions XII. Grid theorem for pinched graphs
( with Bogdan Alecu, Sepehr Hajebi, and Sophie Spirkl)
submitted for publication
Induced subgraphs and tree-decompositions XIII.
Basic obstructions in H -free graphs for finite H $.
( with Bogdan Alecu, Sepehr Hajebi, and Sophie Spirkl)
submitted for publication
Induced subgraphs and tree-decompositions XIV.
Non-adjacent neighbors in a hole.
( with Sepehr Hajebi, and Sophie Spirkl)
to appear in European Journal of Combinatorics
Induced subgraphs and tree-decompositions XV.
Even-hole-free graphs with bounded clique number have logarithmic treewidth.
( with Sepehr Hajebi, Peter Gartland, Daniel Lokshtanov and
Sophie Spirkl)
submitted for publication
Coloring with forbidden induced subgraphs
List-k-coloring H-free graphs for all k>4 ,
( with Sepehr Hajebi and Sophie Spirkl),
to appear in Combinatorica
Reuniting χ-boundedness with polynomial χ-boundedness,
( with Linda Cook, James Davies and Sang-il Oum),
submitted for publication
Polynomial bounds for chromatic number. VI. Adding a four vertex path
( with Alex Scott, Sophie Spirkl and Paul Seymour),
European J. Combinatorics, 110 (2023), 103710
Polynomial bounds for chromatic number. VII. Disjoint holes
( with Alex Scott, Sophie Spirkl and Paul Seymour),
J. Graph Theory, 104 (2023), 499-515
Proof of a conjecture of Plummer and Zha
( with Paul Seymour)
J. Graph Theory, 103 (2023), 437-450
List-three-coloring P_t-free graphs with no induced 1-subdivision
of K_{1,s},
( with Sophie Spirkl and Mingxian Zhong)
Discrete Math, 343 (2020), 112086
Coloring graphs with no induced five-vertex path or gem
( with T. Karthick, P. Maceli and F. Maffray)
Journal of Graph Theory, 95 (2020), 527-542
List-three-coloring graphs with no P6+rP3
( with S. Huang, S. Spirkl, M. Zhong)
Algorithmica (2020)
Triangle-free graphs that do not contain an induced
subdivision of K4 are 3-colorable
( with C.-H. Liu, O. Schaudt, S. Spirkl, N. Trotignon and K. Vuskovic)
Journal of Graph Theory, 92 (2019) 67-95
Four-coloring P_6-free graphs I. Extending an excellent precoloring,
( with S. Spirkl and M. Zhong),
SIAM Journal on Computing, 53 (2024), 111--145.
Four-coloring P_6-free graphs II. Finding an excellent precoloring,
( with S. Spirkl and M. Zhong),
SIAM Journal on Computing, 53 (2024), 146--187.
Obstructions to three-coloring and list-three coloring $H$-free graphs ,
( with J. Goedgebeur, O.Schaudt and M. Zhong),
SIDMA, 34 (2020), 431-469}
3-colorable subclasses of P_8-free graphs
( with Juraj Stacho),
SIDMA 32(2018) 1111-1138
Approximately coloring graphs without long induced paths
( with O. Schaudt, S. Spirkl, M. Stein and M. Zhong),
Algorithmica 81 (2019) 3186-3199
Obstructions for three-coloring free graphs with no paths on six vertices,
( with J. Goedgebeur, O.Schaudt and M. Zhong),
JCT B 140 (2020) 45-83
Three-coloring and list three-coloring of graphs without induced paths on seven vertices, , ( with F. Bonomo, P. Maceli, O.Schaudt, M. Stein, and M. Zhong ),
Combinatorica 38 (2018) 779-801
Induced subgraphs of graphs with large chromatic number II. Three steps towards Gyarfas' conjecture ,
( with Alex Scott and Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 118 (2016), 109-128
Induced subgraphs in graphs of large chromatic number III. Long holes ,
( with Alex Scott and Paul Seymour),
Combinatorica, 37 (2017), 1057-1072
Induced subgraphs in graphs of large chromatic number V. Chandaliers and strings, ,
( with Alex Scott and Paul Seymour),
JCT B, 150 (2021), 195-243.
Induced subgraphs in graphs of large chromatic number VIII. Long odd holes, ,
( with Alex Scott, Paul Seymour and Sophie Spirkl)
JCT B, 140 (2020), 84-97
Induced subgraphs in graphs of large chromatic number IX. Orientations, ,
( with Alex Scott and Paul Seymour)
European Journal of Combinatorics 76 (2019) 53-61
Induced subgraphs in graphs of large chromatic number. XII. Distant Stars ,
( with Alex Scott and Paul Seymour)
JGT 92 (2019) 237-254
Coloring graphs with forbidden induced subgraphs,
Procedings of the ICM, 2014, 292-302
4-coloring P6-free graphs with no induced 5-cycles
( with Peter Maceli, Juraj Stacho and Mingxian Zhong),
Journal of Graph Theory, 84 (2017), 262-285
Flag Spheres
Induced equators in flag spheres
( with Eran Nevo),
Journal of Combinatorial Theory, Ser A, 176 (2020), 105283
Stable sets in flag spheres
( with Eran Nevo),
European J Combinatorics, 110 (2023), 103699
Other papers on forbidden induced subgraphs
Counting independent sets in structured graphs
( with Matija Buci\'c and Julien Codsi)
( submitted for publication )
Graphs with no even holes and no sector wheels are the union of two chordal graphs
( with Tara Abrishami, Eli Berger and Shira Zerbib)
( European Journal of Combinatorics, 122 (2024), 104035.)
Cops and robbers in P_5-free graphs
( with Sergey Norin, Paul Seymour and Jeremie Turcotte),
( SIDMA, 38 (2024), 845-856)
Strengthening Rodl's theorem
( with Alex Scott, Paul Seymour and Sophie Spirkl),
( Journal of Combinatorial Theory, Ser. B, 163 (2023), 256-271)
Subdivided claws and the clique-stable set separation problem
( with Paul Seymour)
( in D. Wood, J. de Gier, C. Praeger, T.Tao (eds) 2019-2020 MATRIX Annals, Springer, 2020.)
Square-free graphs with no induced fork
( with S. Huang, T. Karthick and J. Kaufmann)
( Electronic Journal of Combinatorics, 28 (2021) )
Excluding the fork and the antifork
( with L. Cook and P. Seymour)
( Discrete Math, 343 (2020), Article 111786 )
Proof of the Kalai-Meshulam conjecture
( with A. Scott, P. Seymour and S. Spirkl),
( Israel Journal of Math, 238 (2020), 639--661. )
Triangle-free graphs with no six-vertex induced path.
( with P. Seymour, S.Spirkl and M. Zhong),
( Discrete Math 341 (2018) 2179-2196).
The sandwich problem for decompositions and almost monotone properties
( with C.M.H. de Figueiredo and S. Spirkl),
Algorithmica 12 (2018), 3618-3645
Piercing axes-parallel boxes , ( with Sophie Sprikl and Shira Zerbib),
European Journal of Combinatorics 25 (2018) P1.70
Unavoidable induced subgraphs in large
graphs with no homogeneous sets , ( with Ringi Kim, Sang-il Oum and
Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 118 (2016), 1-12
Wheel-free planar graphs,
( with Pierre Aboulker, Paul Seymour and Nicolas Trotgnon)
European Journal of Combinatorics (2015),
pp. 57-67
Large cliques and stable sets in undirected graphs ,
Geometry, Structure and Randomness in Combinatorics,
Publications of the Scuola Normale Superiore / CRM Series,
(eds: J. Matousek, J. Nesetril and M. Pellegrini), Edizioni della Normale
Excluding pairs of graphs
( with Alex Scott and Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 106(2014), 15-29
Graphs with no induced five-vertex path or antipath ,
( with L. Esperet, L. Lemoine, P. Maceli, F. Maffray and I. Penev),
Journal of Graph Theory, 84 (2017), 221-232
Cliques in the union of graphs
( with Ron Aharoni,Eli Berger and Juba Ziani),
Journal of Combinatorial Theory, Ser. B, 114 (2015), 170-186
Simplicial vertices in graphs with no induced four-edge path or four-edge antipath, and the H_6-conjecture
( with Peter Maceli),
Journal of Graph Theory, 76 (2014), 249-261
Excluding a substar and an antisubstar
( with Sergey Norin, Bruce Reed and Paul Seymour),
SIDMA, 29 (2015), 297-308
Rao's conjecture on degree sequences
( with Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 105 (2014), 44-92
Substitution and χ-boundedness ( with Irena Penev, Alex Scott and Nicolas
Trotignon)
Journal of Combinatorial Theory, Ser. B, 103 (2013), 567-586
$K_4$-free graphs with no odd holes
( with N. Robertson, P.Seymour and R. Thomas),
Journal of Combinatorial Theory, Ser. B, 100 (2010), 313-331
Excluding induced subgraphs
( with Paul Seymour), Surveys in Combinatirics 2007,
London Math Soc Lecture Note Series, 346, 99-119
Bisimplicial vertices in even-hole-free graphs
( with L. Addario-Berry, F. Havet, B. Reed and P. Seymour),
Journal of Combinatorial Theory, Ser. B, 98 (2008), 1119-1164
with an erratum
Even-hole-free graphs still have bisimplicial vertices
( with Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 161 (2023), 331--381
Solution of three problems of Cornuejols
( with Paul Seymour), Journal of Combinatorial Theory, Ser. B,
98 (2008), 116-135
Algorithms for detecting induced subgraphs
Finding a shortest odd hole
( with A. Scott, P. Seymour)
ACM Transactions on Algorithms, 17 (2021), 1--21
Detecting a long odd hole
( with A. Scott, P. Seymour)
Combinatorica, 41 (2021), 1--30
Detecting an odd hole
( with A. Scott, P. Seymour and S. Spirkl)
JACM 67 (2020), Article 5
Detecting and induced net subdivision
( with P. Seymour and N. Trotignon),
Journal of Combinatorial Theory, Ser. B, 103 (2013), 643-641
Detecting Even Holes
( with K. Kawarabayashi and P. Seymour),
Journal of Graph Theory 48(2005), 85-111
The three-in-a-tree problem
( with Paul Seymour),
Combinatorica, 30 (2010), 387-417
Detecting a theta or a prism
( with Rohan Kapadia),
SIAM Journal on Discrete Math 22(2008), 1164-1186
Optimization problems in graphs with forbidden induced subgraphs
Max weight independent set in sparse graphs with no long claws
( with Tara Abrishami, Cemil Dibek, Marcin Pilipczuk and Pawel Rzazewski),
journal version; submitted for publication
Sparse induced subgraphs in P_6-free graphs,
( with Rose McCarty, Marcin Pilipczuk, Mihal Pilipczuk and Pawel Rzazewski)
journal version; submitted for publication
Polynomial-time algorithm for maximum independent set in graphs with no long induced claws,
( with Tara Abrishami, Cemil Dibek and Pawel Rzazewski),
manuscript
Finding large $H$-colorable subgraphs in hereditary graph classes,
( with J. King, Mihal Pilipczuk, P. Rzazewski and S. Spirkl),
SIAM Journal on Discrete Math 35(2021), 2367-2386
Graphs with polynomially many minimal separators
( with T. Abrishami, C. Dibek, N. Trotignon, S. Thomasse and K.Vuskovic),
Journal of Combinatorial Theory, Ser. B, 152 (2022), 248-280.
Induced subgraphs of bounded treewidth and the container method
( with T. Abrishami, M. Pilipczuk, P. Rzazewski and P. Seymour),
SAIM Journal on Computing, 53 (2024), 10.1137/20M1383732.
Maximum independent sets in (pyramid, even hole)-free graphs
( with N. Trotignon, S. Thomasse and K.Vuskovic),
manuscript
Qausi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
( with Marcin Pilipczuk, Mihal Pilipczuk and S. Thomasse)
SIAM Journal on Computing, 53 (2024), 47--86.
On the maximum weight independent set problem in graph without induced cycles of length at least five
( with M. Pilipczuk, M. Pilipczuk and S. Thomasse),
SIDMA, 34 (2020), 1472-1483
The Caccetta-Haggkvist Conjecture
Non-uniform degrees and rainbow versions of the Caccetta-Haggkvist conjecture
( with Ron Aharoni, Eli Berger, He Guo and Shira Zerbib),
SIDMA, 37 (2023), 1704 - 1714
Cycles in dense digraphs
( with Paul Seymour and Blair Sullivan),
Combinatorica 28(2008), 1-18
The Erdos-Hajnal Conjecture
Erdos-Hajnal for graphs with no 5-hole
( with A. Scott, P. Seymour and S.Spirkl),
Proceedings of the London Mathematical Society, 126 (2023), 997-1014