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

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 an erratum to appear in JCT B


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


Coloring with forbidden induced subgraphs

List-three-coloring graphs with no P6+rP3 ( with S. Huang, S. Spirkl, M. Zhong) submitted for publication

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

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

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

Obstructions to 3-coloring P_6-free graphs , ( with J. Goedgebeur, O.Schaudt and M. Zhong), submitted for publication

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 ), appeared on-line in Combinatorica (2017), DOI:10.1007/s00493-017-3553-8

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

Induced subgraphs in graphs of large chromatic number IX. Orientations, , ( with Alex Scott and Paul Seymour) submitted for publication

Induced subgraphs in graphs of large chromatic number. XII. Distant Stars , ( with Alex Scott and Paul Seymour) submitted for publication

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

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

Solution of three problems of Cornuejols ( with Paul Seymour), Journal of Combinatorial Theory, Ser. B, 98 (2008), 116-135


Algorithms for detecting induced subgraphs

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


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

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

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

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

Vertex-minors and the Erdos-Hajnal conjecture ( with} Sang-il Oum ), submitted for publication

Towards Erdos-Hajnal for graphs with no 5-hole ( with Jacob Fox, Alex Scott, Paul Seymour and Sophie Spirkl), submitted for publications

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

Domination in tournaments , ( with Ringi Kim, Chun-Hung Liu, Paul Seymour and Stephan Thomasse), submitted for publication

Disjoint paths in unions of tournaments, ( with Alex Scott and Paul Seymour), submitted for publication

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

6-vertex tournaments and the Erdos-Hajnal Conjecture ( with Eli Berger and Krzysztof Choromanski), submitted for publications

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

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

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