publi Papers available on-line

Papers available on-line

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), to appear in JCT B

Decomposing and clique-coloring (Diamond, Odd-hole)-free graphs ( with Irene Lo), Journal of Graph Theory, 86 (2017), 5-41

Coloring sqaure-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), submitted for publication


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), submitted for publication

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


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


Coloring with forbidden induced subgraphs

List-three-coloring P_t-free graphs with no induced 1-subdivision of K_{1,s}, ( with Sophie Spirkl and Mingxian Zhong) to appear in Discrete Math

Coloring graphs with no induced five-vertex path or gem ( with T. Karthick, P. Maceli and F. Maffray) to appear in Journal of Graph Theory

List-three-coloring graphs with no P6+rP3 ( with S. Huang, S. Spirkl, M. Zhong) to appear in Algorithmica

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), submitted for publication

Four-coloring P_6-free graphs II. Finding an excellent precoloring, ( with S. Spirkl and M. Zhong), submitted for publication

Obstructions to three-coloring and list-three coloring $H$-free graphs , ( with J. Goedgebeur, O.Schaudt and M. Zhong), to appear in SIDMA

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), submitted for publication

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


Other papers on forbidden induced subgraphs

Even-hole-free graphs of bounded degree have bounded treewidth ( with Tara Abrishami and Kristina Vuskovic) ( submitted for publication)

Subdivided claws and the clique-stable set separation problem ( with Paul Seymour) ( submitted for publication)

Sqaure-free graphs with no induced fork ( with S. Huang, T. Karthick and J. Kaufmann) ( submitted for publication)

Excluding the fork and 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), ( submitted for publication )

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), to appeared on-line in Algorithmica

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) submitted for publication

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), submitted for publication

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) submitted for publiation

Detecting a long odd hole ( with A. Scott, P. Seymour) submitted for publiation

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

Finding large $H$-colorable subgraphs in hereditary graph classes, ( with J. King, Mihal Pilipczuk, P. Rzazewski and S. Spirkl), submitted for publication

Graphs with polynomially many minimal separators ( with T. Abrishami, C. Dibek, N. Trotignon, S. Thomasse and K.Vuskovic), submitted for publication

Induced subgraphs of bounded treewidth and the container method ( with T. Abrishami, M. Pilipczuk, P. Rzazewski and P. Seymour), manuscript

Maximum independent sets in (pyramid, even hole)-free graphs ( with N. Trotignon, S. Thomasse and K.Vuskovic), manuscript

Qauso-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs ( with Marcin Pilipczuk, Mihal Pilipczuk and S. Thomasse) submitted for publication

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), submitted for publication


A paper related to the Caccetta-Haggkvist Conjecture

Cycles in dense digraphs ( with Paul Seymour and Blair Sullivan), Combinatorica 28(2008), 1-18


The Erdos-Hajnal Conjecture

Holes with hats and Erdos-Hajnal , ( with P. Seymour), submitted for publication

Pure pairs I. Trees and linear anticomplete pairs. ( with A. Scott, P. Seymour and S.Spirkl), submitted for publication

Pure pairs II, Sparse graphs without linear anticomplete pairs, ( with A. Scott, P. Seymour and S.Spirkl), submitted for publication

Pure pairs III. Sparse graphs without polynomial-size anticomplete pairs, ( with J. Fox, A. Scott, P. Seymour and S.Spirkl), submitted for publication

Vertex-minors and the Erdos-Hajnal conjecture ( with} Sang-il Oum ), Discrete Math 341 (2018) 3498-3499

Towards Erdos-Hajnal for graphs with no 5-hole ( with Jacob Fox, Alex Scott, Paul Seymour and Sophie Spirkl), Combinatorica 39 (2019) 983-991

Excluding Paths and Antipaths ( with Paul Seymour), Combinatorica 35(2015), 389-412

The Erdos-Hajnal conjecture---A Survey Journal of Graph Theory, 75 (2014), 178-190

Extending the Gyarfas-Sumner conjecture ( with Paul Seymour), Journal of Combinatorial Theory, Ser. B, 105 (2014), 11-16

Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement ( with Yori Zwols), Journal of Graph Theory, 70 (2012), 449-472

The Erdos-Hajnal Conjecture for bull-free graphs ( with Shmuel Safra), Journal of Combinatorial Theory, Ser. B, 98 (2008), 1301-1310


Tournaments

Tournaments and the strong Erdos-Hajnal property , ( with E. Berger, K. Choromanski and S. Zerbib), submitted for publication

Domination in tournaments , ( with Ringi Kim, Chun-Hung Liu, Paul Seymour and Stephan Thomasse), JCT B 130 (2018) 98-113

Disjoint paths in unions of tournaments, ( with Alex Scott and Paul Seymour), JCT B 135 (2019) 238-255

Tournaments with near-linear transitive subsets ( with Krzysztof Choromanski and Paul Seymour), Journal of Combinatorial Theory, Ser. B, 109 (2014), 228-249

On the Erdos-Hajnal Conjecture for six-vertex tournaments ( with Eli Berger and Krzysztof Choromanski), European Journal of Combinatorics 75 (2019) 113-122

Forcing Large Transitive Subtournaments ( with Eli Berger and Krzysztof Choromanski), Journal of Combinatorial Theory, Ser. B, 113 (2015), 1-17

A counterexample to a conjecture of Schwartz ( with Felix Brandt, Ilhee Kim, Gaku Liu, Sergey Norin, Alex Scott, Paul Seymour and Stephan Thomasse), Social Choice and Welfare, 40 (2013), 739-743

Tournaments and Coloring ( with Eli Berger, Krzysztof Choromanski, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour and Stephan Thomasse), Journal of Combinatorial Theory, Ser. B, 103 (2013), 1-20

Disjoint paths in tournaments ( with Alex Scott and Paul Seymour), Advances in Mathematics, 270 (2015), 582-597

Tournament immersion and cutwidth ( with Alexandra Fradkin and Paul Seymour), to appear in Journal of Combinatorial Theory, Ser. B

A well-quasi-order for tournaments ( with Paul Seymour), Journal of Combinatorial Theory, Ser. B, 101 (2011), 47-53


Other

Small families under subdivision ( with M. Loebl and P. Seynur), manuscript

Concatenating bipartite graphs ( with A. Scott, P. Seymour and S. Spirkl), submitted for publication

Cooperative colorings of trees and of bipartite graphs. ( with Ron Aharoni, Eli Berger, Frederic Havet and Zilin Jiang) submitted for publication

Large rainbow matchings in general graphs ( with R. aharoni, E. Berger, D. Howard and P. Seymour) European Journal of Combinatorics 72 (2019) 222-227

Disjoint dijoins ( with Katherine Edwards, Ringi Kim, Alex Scott and Paul Seymour), ( Journal of Combinatorial Theory, Ser. B, 120 (2016), 18-35 )

Immersion in four-edge-connected graphs ( with Zdenek Dvorak, Tereza Klimosova and Paul Seymour) ( Journal of Combinatorial Theory, Ser. B, 116 (2016), 208-218 )

Edge-coloring 7-regular planar graphs ( with Katherine Edwards, Ken-ichi Kawarabayashi and Paul Seymour) Journal of Combinatorial Theory, Ser. B, 115 (2015), 276-302

Edge-coloring 8-regular planar graphs ( with Katherine Edwards, Ken-ichi Kawarabayashi and Paul Seymour) Journal of Combinatorial Theory, Ser. B, 115 (2015), 303-338

Lines in hypergraphs ( with L.Beaudou, A.Bondy, X.Chen, E.Chiniforooshan, V. Chvatal, N. Fraiman, and Y. Zwols) Combinatorica, 33 (2013), 633-654

A De Bruijn-Erdos theorem for chordal graphs ( with L.Beaudou, A.Bondy, X.Chen, E.Chiniforooshan, V. Chvatal, N. Fraiman, and Y. Zwols) Electronic Journal of Combinatorics, 22 (2015), 1.70

Analyzing the performance of greedy maximal scheduling via local pooling and graph theory (conference version) ( with Berk Birand, Paul Seymour, Bernard Ries, Gil Zussman and Yori Zwols, ( IEEE/ACM Trans. Netw. 20 (2012),163--176. )

Packing seagulls ( with Paul Seymour), Combinatorica, 32 (2012), 251-282

Finding minimum clique capacity ( with Sang-il Oum and Paul Seymour), Combinatorica, 32 (2012), 283-287

The edge density for K_{2,t} minors ( with Bruce Reed and Paul Seymour), Journal of Combinatorial Theory, Ser. B, 101 (2011), 18-46

Perfect matchings in planar cubic graphs ( with Paul Seymour), Combinatorica, (2012), 403-424

Non-zero A-paths in graphs with edges labeled by group elements ( with Jim Geelen, Bert Gerards, Luis Goddyn, Michael Lohman, and Paul Seymour), Combinatorica, 26(2006), 521-532

An algorithm for packing non-zero $A$-paths in group-labeled graphs ( with William H. Cunningham and Jim Geelen), Combinatorica 28(2008), 145-161

Partial characterizations of clique-perfect graphs I : claw-free graphs ( with Flavia Bonomo and Guillermo Duran), Discrete Applied Mathematics 156 (2008), 1058-1082

Partial characterizations of clique-perfect graphs II : diamond-free and Helly circular-arc graphs ( with Flavia Bonomo and Guillermo Duran), to appear in Discrete Mathematics