Perfect Graphs
The Strong Perfect Graph Theorem (with N.Robertson, P.Seymour,
R.Thomas), Annals of Math, 164(2006), 51-229
Recognizing Berge Graphs
( with G.Cornuejols, X.Liu, P.Seymour, K. Vuskovic),
Combinatorica, 25(2005), 143-187
Berge Trigraphs,
Journal of Graph Theory, 53(2006), 1-55
Even Pairs in Berge Graphs
( with P.Seymour),
Journal of Combinatorial Theory, Ser. B, 99 (2009), 370-377
Three-colorable perfect graphs without even
pairs
( with P.Seymour),
Journal of Combinatorial Theory. Ser B, 102 (2012), 363-394
Coloring perfect graphs with no balanced
skew-partitions ( with Nicolas Trotignon, Theophile
Trunck and Kristina Vuskovic),
Journal of Combinatorial Theory, Ser B 115 (2015), 26-65
Decomposing and clique-coloring (Diamond, Odd-hole)-free graphs
( with Irene Lo),
Journal of Graph Theory, 86 (2017), 5-41
Coloring square-free Berge graphs
( with Irene Lo, Frederic Maffray, Nicolas Trotignon and Kristina Vuskovic), JCT B, 135 (2019), 96-128
Coloring perfect graphs with bounded clique number
( with Aurelie Lagoutte, Paul Seymour and Sophie Spirkl),
JCT B 122 (2017), 757-775
A Short Proof of the Wonderful Lemma ,
Journal of Graph Theory, 87 (2018), 271-274
Even pairs and prism corners in Berge graphs
,
( with F. Maffray, P. Seymour and S.Spirkl),
Journal of Combinatorial Theory, Ser B, 131 (2018), 12-39. with a corrighendum JCT B 133 (2018) 259-260
Strongly perfect claw-free grpahs-a short proof
,
( with C. Dibek),
Journal of Graph Theory, 97 (2021), 359-381
Submodilar functions and perfect graphs,
( with T. Abrishami, C. Dibek and K. Vuskovic),
to appear in Mathematics of Operations Research
Attempting perfect hypergraphs,
( with G. Kalai),
Israel Journal of Mathematics, 256 (2023), 133-151
Even pairs in perfect graphs with no balanced skew-partitions,
( with Tara Abrishami and Yaqian Tang),
Discrete Math, 348 (2025), 114388
Claw-free Graphs
The Structure of Claw-free Graphs
( with Paul Seymour), Surveys in Combinatirics 2005,
London Math Soc Lecture Note Series, 327, 153-171
The Roots of The Stable Set Polynomial of a
Claw-free Graph ( with Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 97 (2007), 350-357
Claw-free Graphs I. Orientable prismatic graphs
( with Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 97 (2007), 867-901
Claw-free Graphs II. Non-orientable prismatic graphs
( with Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 98 (2008), 249-290
Claw-free Graphs III. Circular Interval Graphs
( with Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 98 (2008), 812-834
Claw-free Graphs IV. Decomposition theorem
( with Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 98 (2008), 839-938
Claw-free Graphs V. Global structure
( with Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 98 (2008), 1373-1410
Claw-free Graphs VI. Coloring claw-free graphs.
( with Paul Seymour),
Journal of Combinatorial Theory, Ser. B, 100 (2010), 560-572
Claw-free Graphs VII. Quasi-line graphs
( with Paul Seymour), Journal of Combinatorial Theory, Ser. B, 102 (2012), 1267-1294
Coloring quasi-line graphs
( with Alexandra Ovetsky), Journal of Graph Theory,
54(2007), 41-50
Hadwiger's conjecture for quasi-line
graphs
( with Alexandra Ovetsky Fradkin),
Journal of Graph Theory 59 (2008), 17-33
An approximate version of Hadwiger's
conjecture for claw-free graphs
( with Alexandra Ovetsky Fradkin),
Journal of Graph Theory, 63 (2010), 259-278
Claw-free graphs with strongly perfect
complements.Fractional and integral version. Part I. Basic graphs
( with Bernard Ries and Yori Zwols),
Discrete Applied Math, 159(2011), 1971-1995
Claw-free graphs with strongly perfect
complements.Fractional and integral version. Part II. Nontrivial strip
structures
( with Bernard Ries and Yori Zwols),
Discrete Applied Math, 159(2011), 1996-2029
Growing without cloning
( with Paul Seymour), SIDMA, 26 (2012), 860-880
A local strengthening of Reed's ω, Δ, χ
conjecture for quasi-line graphs
( with Andrew D. King, Matthieu Plumettaz and Paul Seymour), SIDMA, 27 (2013), 95-108
Optimal anti-thickenings of claw-free graphs
( with Andrew D. King), manuscript
The structure of claw-free perfect graphs
( with Matthieu Plumettaz),
Journal of Graph Theory, 75 (2014), 203-230
On the Erdos-Lovasz Tihany Conjecture for Claw-Free Graphs
( with Matthieu Plumettaz and Alexandra Fradkin),
manuscript
A note on simplicial cliques
( with A. Scott, P. Seymour and S. Spirkl),
Discrete Math, 344 (2021), 112470
Bull-free Graphs
The structure of bull-free graphs I---
three-edge paths with centers and anticenters
Journal of Combinatorial Theory, Ser. B,
102 (2012), 233-251
The structure of bull-free graphs II and III---
a summary
Journal of Combinatorial Theory, Ser. B,
102 (2012), pp. 252-282
The structure of bull-free graphs II---
elementary trigraphs
manuscript
The structure of bull-free graphs III---
global structure
manuscript
Excluding induced subdivisions of the bull and
related graphs ( with Irena Penev, Alex Scott and Nicolas
Trotignon) Journal of Graph Theory, 71 (2012): 49-68
The structure of bull-free perfect graphs
( with Irena Penev) Journal of Graph Theory, 74 (2013), 1-31
Odd holes in bull-free graphs
( with Vaidy Sivaraman),
SIDMA, 32 (2018): 951-955
Perfect divisibility and 2-divisibility
( with Vaidy Sivaraman),
JGT, 90 (2018) 54-60
Tree-independence number
On treewidth and maximum cliques.
(with Nicolas Trotignon),
submitted for publication
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
Tree independence number IV. Even-hole-free graphs. ,
(with Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov and Sophie Spirkl),
submitted for publication
Tree independence number V. Walls and claws. ,
(with Julien Codsi, Daniel Lokshtanov, Martin Milanic and Varun Sivashankar), 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)
Combinatorica, 44 (2024), 921--948.
Induced subgraphs and tree-decompositions IX. Grid theorem for perforated graphs
( with Bogdan Alecu, Sepehr Hajebi, and Sophie Spirkl)
to appear in Advances in Combinatorics
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)
to appear in Innovations in Graph Theory
Induced subgraphs and tree-decompositions XIII.
Basic obstructions in H -free graphs for finite H $.
( with Bogdan Alecu, Sepehr Hajebi, and Sophie Spirkl)
to appear in Advances in Combinatorics
Induced subgraphs and tree-decompositions XIV.
Non-adjacent neighbors in a hole.
( with Sepehr Hajebi, and Sophie Spirkl)
European Journal of Combinatorics, 124 (2025), 104074
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
Induced subgraphs and tree-decompositions XVI.
Complete bipartite induced minors.
( with Sepehr Hajebi, and Sophie Spirkl)
submitted for publication
Induced subgraphs and tree-decompositions XVII.
Anticomplete sets of large treewidth.
( with Sepehr Hajebi, and Sophie Spirkl)
submitted for publication
Induced subgraphs and tree-decompositions XVIII.
Obstructions to bounded pathwidth.
( with Sepehr Hajebi, and Sophie Spirkl)
submitted for publication
Coloring with forbidden induced subgraphs
Colouring t-perfect graphs ,
( with Linda Cook, James Davies, Sang-il Oum and Jane Tan),
submitted for publication
List-k-coloring H-free graphs for all k>4 ,
( with Sepehr Hajebi and Sophie Spirkl),
Combinatorica, 44 (2024), 1063-1068
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)
( to appear in Combinatorics, Probability and Compuiting )
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