P. Aboulker, J. Bang-jensen, N. Bousquet, P. Charbit, F. Havet et al., ?-bounded families of oriented graphs, Journal of Graph Theory, vol.89, pp.304-326, 2018.

P. Aboulker, P. Charbit, and R. Naserasr, Digraph Coloring and extension of Gyarfas-Sumner conjecture

P. Aboulker, P. Charbit, N. Trotignon, and K. Vu?kovi?, Vertex elimination orderings for hereditary graph classes, Discrete Mathematics, vol.338, pp.825-834, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01230783

P. Aboulker, M. Radovanovic, N. Trotignon, and K. Vu?kovi?, Graphs that do not contain a cycle with a node that has at least two neighbors on it, SIAM Journal on Discrete Mathematics, vol.26, pp.1510-1531, 2012.
URL : https://hal.archives-ouvertes.fr/ensl-00800037

L. Addario-berry and M. Chudnovsky, Bisimplicial vertices in even-hole-free graphs, J. Combin. Theory Ser. B, vol.98, pp.1119-1164, 2008.

L. Addario-berry, F. Havet, C. Sales, B. Reed, and S. Thomassé, Oriented trees in digraphs, Discrete Mathematics 313, vol.8, pp.967-974, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00821609

P. Afshani and T. M. Chan, Approximation Algorithms for Maximum Cliques in 3D Unit-Disk Graphs, Proceedings of the 17th Canadian Conference on Computational Geometry, CCCG'05, pp.19-22, 2005.

P. Afshani and H. Hatami, Approximation and inapproximability results for maximum clique of disc graphs in high dimensions, Inf. Process. Lett, vol.105, issue.3, pp.83-87, 2008.

K. Pankaj, M. Agarwal, S. Van-kreveld, and . Suri, Label placement by maximum independent set in rectangles, Computational Geometry, vol.11, pp.209-218, 1998.

R. Aharoni and P. Haxell, Hall's theorem for hypergraphs, Journal of Graph Theory, vol.35, pp.83-88, 2000.

J. Alber and J. Fiala, Geometric separation and exact solutions for the parameterized independent set problem on disk graphs, J. Algorithms, vol.52, pp.134-151, 2004.

V. , The Effect of Local Constraints on the Complexity of Determination of the Graph Independence Number, Combinatorial-Algebraic Methods in Applied Mathematics, pp.3-13, 1982.

C. Ambühl and U. Wagner, The Clique Problem in Intersection Graphs of Ellipses and Triangles, Theory Comput. Syst, vol.38, pp.279-292, 2005.

T. Andreae, M. Schughart, and Z. Tuza, Clique-transversal sets of line graphs and complements of line graphs, Discrete Mathematics, vol.88, pp.11-20, 1991.

M. Evgeniy and . Andreev, On convex polyhedra in Lobachevskii spaces, Matematicheskii Sbornik, vol.123, pp.445-478, 1970.

R. Arratia, B. Bollobás, D. Coppersmith, and G. B. Sorkin, Euler circuits and DNA sequencing by hybridization, Discrete Applied Mathematics, vol.104, pp.63-96, 2000.

S. Artmann, R. Weismantel, and R. Zenklusen, A strongly polynomial algorithm for bimodular integer linear programming, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.1206-1219, 2017.

A. Atminas and V. Zamaraev, On forbidden induced subgraphs for unit disk graphs, Discrete & Computational Geometry, pp.1-41, 2018.

M. Avriel, M. Penn, and N. Shpirer, Container ship stowage problem: complexity and connection to the coloring of circle graphs, Discrete Applied Mathematics, vol.103, pp.271-279, 2000.

G. Bacsó, D. Lokshtanov, D. Marx, M. Pilipczuk, Z. Tuza et al., Subexponential-time Algorithms for Maximum Independent Set in P t -free and Broomfree Graphs, 2018.

G. Bacsó and S. Gravier, András Gyárfás, Myriam Preissmann, and András Sebo, SIAM Journal on Discrete Mathematics, vol.17, pp.361-376, 2004.

J. Bang-jensen, B. Reed, M. Schacht, R. ?ámal, B. Toft et al., On six problems posed by Jarik Ne?et?il, Topics in Discrete Mathematics, pp.613-627, 2006.

J. Beisegel, C. Denkert, E. Köhler, M. Krnc, N. Piva? et al., On the End-Vertex Problem of Graph Searches, 2018.

C. Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wissenschaftliche Zeitschrift, 1961.

E. Berger, K. Choromanski, M. Chudnovsky, J. Fox, M. Loebl et al., Tournaments and colouring, Journal of Combinatorial Theory, Series B, vol.103, pp.1-20, 2013.

A. Berry, R. S. Jean, J. Blair, G. Bordat, and . Simonet, Graph extremities defined by search algorithms, Algorithms, vol.3, issue.2, pp.100-124, 2010.
URL : https://hal.archives-ouvertes.fr/lirmm-00106696

A. Berry and J. Bordat, Separability generalizes Dirac's theorem, Discrete Applied Mathematics, vol.84, pp.43-53, 1998.

D. Bienstock, On the complexity of testing for odd holes and induced odd paths, Discrete Mathematics, vol.90, pp.85-92, 1991.

C. Biró, É. Bonnet, D. Marx, T. Miltzow, and P. Rz??ewski, Fine-Grained Complexity of Coloring Unit Disks and Balls, 33rd International Symposium on Computational Geometry, vol.18, p.16, 2017.

A. Bock, Y. Faenza, C. Moldenhauer, and A. J. Ruiz-vargas, Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, pp.187-198, 2014.

D. Bokal, G. Fijavz, M. Juvan, B. Mark-kayll, and . Mohar, The circular chromatic number of a digraph, Journal of Graph Theory, vol.46, pp.227-240, 2004.

M. Bonamy, E. Bonnet, N. Bousquet, P. Charbit, and S. Thomassé, EPTAS for Max Clique on Disks and Unit Balls, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pp.568-579, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01962198

M. Bonamy, P. Charbit, and S. Thomassé, Graphs with large chromatic number induce 3k-cycles, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01431393

V. Boncompagni, M. Radovanovi?, and K. Vu?kovi?, The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs, Journal of Graph Theory

É. Bonnet, N. Bousquet, P. Charbit, S. Thomassé, and R. Watrigant, Parameterized Complexity of Independent Set in H-Free Graphs, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01962369

, QPTAS and Subexponential Algorithm for Maximum Clique on Disk, 2018.

A. Bouchet, Circle Graph Obstructions, Journal of Combinatorial Theory, Series B, vol.60, pp.107-144, 1994.

A. Brandstãdt, V. B. Le, and J. P. Spinrad, Graph Classes: A Survey. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 1999.

A. Brandstädt, F. Feodor, F. Dragan, and . Nicolai, LexBFS-orderings and powers of chordal graphs, Discrete Mathematics, vol.171, pp.27-42, 1997.

A. Brandstädt and C. T. Hoàng, Maximum Induced Matchings for Chordal Graphs in Linear Time, Algorithmica 52, vol.4, pp.440-447, 2008.

A. Bretscher, D. Corneil, M. Habib, and C. Paul, A Simple Linear Time LexBFS Cograph Recognition Algorithm, Graph-Theoretic Concepts in Computer Science, pp.119-130, 2003.
URL : https://hal.archives-ouvertes.fr/lirmm-00269525

H. Breu and D. G. Kirkpatrick, Unit disk graph recognition is NP-hard, Comput. Geom, vol.9, issue.1-2, pp.3-24, 1998.

A. Stefan and . Burr, Subtrees of directed graphs and hypergraphs, Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing, vol.28, pp.227-239, 1980.

S. Cabello, Maximum clique for disks of two sizes. Open problems from Geometric Intersection Graphs: Problems and Directions CG Week Workshop, 2015.

S. Cabello, Open problems presented at the Algorithmic Graph Theory on the Adriatic Coast workshop, 2015.

J. Chalopin, D. Gonçalves, and P. Ochem, Planar Graphs Have 1-string Representations, Discrete & Computational Geometry, vol.43, issue.3, pp.626-647, 2010.
URL : https://hal.archives-ouvertes.fr/lirmm-00433091

T. M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms, vol.46, pp.178-189, 2003.

P. Charbit, M. Habib, V. Limouzy, F. De-montgolfier, M. Raffinot et al., A note on computing set overlap classes, Information Processing Letters, vol.108, pp.186-191, 2008.
URL : https://hal.archives-ouvertes.fr/lirmm-00325371

P. Charbit, M. Fabien-de-montgolfier, and . Raffinot, Linear time split decomposition revisited, SIAM Journal on Discrete Mathematics, vol.26, pp.499-514, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00921774

P. Charbit, M. Habib, and A. Mamcarz, Influence of the tie-break rule on the end-vertex problem, Discrete Mathematics & Theoretical Computer Science, vol.16, pp.57-72, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01101514

P. Charbit, M. Habib, L. Mouatadid, and R. Naserasr, A New Graph Parameter to Measure Linearity, Combinatorial Optimization and Applications -11th International Conference, pp.154-168, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01672521

P. Charbit, M. Habib, N. Trotignon, and K. Vu?kovi?, Detecting 2-joins faster, Journal of discrete algorithms, vol.17, pp.60-66, 2012.

P. Charbit, M. Fabien-de-montgolfier, and . Raffinot, A Simple Linear Time Split Decomposition Algorithm of Undirected Graphs, 2009.

P. Charbit, I. Penev, S. Thomassé, and N. Trotignon, Perfect graphs of arbitrarily large clique-chromatic number, Journal of Combinatorial Theory, Series B, vol.116, pp.456-464, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01324052

M. Chein, M. Habib, and M. Maurer, Partitive hypergraphs, Discrete Mathematics, vol.37, pp.35-50, 1981.

M. Chudnovsky, A. Lagoutte, P. Seymour, and S. Spirkl, Colouring perfect graphs with bounded clique number, Journal of Combinatorial Theory.Series B, vol.122, pp.757-775, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01561528

M. Chudnovsky, Berge trigraphs, Journal of Graph Theory, vol.53, issue.1, pp.1-55, 2006.

M. Chudnovsky and I. Lo, Decomposing and Clique-Coloring Diamond, Odd-Hole-Free Graphs, J. Graph Theory, vol.86, pp.5-41, 2017.

M. Chudnovsky, I. Lo, F. Maffray, N. Trotignon, and K. Vu?kovi?, Coloring square-free Berge graphs, Journal of Combinatorial Theory, Series B, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01993462

M. Chudnovsky, N. Robertson, P. D. Seymour, and R. Thomas, The Strong Perfect Graph Theorem, Annals of Mathematics, vol.164, issue.1, pp.51-229, 2006.

M. Chudnovsky, A. Scott, and P. Seymour, Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures, Journal of Combinatorial Theory, Series B, vol.118, pp.109-128, 2016.

M. Chudnovsky, A. Scott, and P. Seymour, Induced subgraphs of graphs with large chromatic number. III. Long holes, Combinatorica 37, vol.6, pp.1057-1072, 2017.

M. Chudnovsky, A. Scott, and P. Seymour, Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings, 2016.

M. Chudnovsky, A. Scott, and P. Seymour, Induced subgraphs of graphs with large chromatic number. XI. Orientations, European Journal of Combinatorics, vol.76, pp.53-61, 2019.

M. Chudnovsky, A. Scott, and P. Seymour, Induced subgraphs of graphs with large chromatic number. XII. Distant stars, 2017.

M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl, Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes, 2017.

M. Chudnovsky and P. D. Seymour, The structure of claw-free graphs, Surveys in combinatorics 2005, vol.327, pp.153-171, 2005.

M. Chudnovsky and P. Seymour, Claw-free graphs. IV. Decomposition theorem, Journal of Combinatorial Theory, Series B, vol.98, pp.839-938, 2008.

M. Chudnovsky and P. Seymour, Claw-free graphs. V. Global structure, Journal of Combinatorial Theory, Series B, vol.98, pp.1373-1410, 2008.

M. Chudnovsky, D. Paul, and . Seymour, The structure of claw-free graphs, In: Surveys in combinatorics, vol.327, pp.153-171, 2005.

M. Chudnovsky, N. Trotignon, T. Trunck, and K. Vu?kovi?, Coloring perfect graphs with no balanced skew-partitions, Journal of Combinatorial Theory, Series B, vol.115, pp.26-65, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01222922

M. Chudnovsky, *. , G. Cornuéjols, *. , X. Liu et al., Recognizing Berge Graphs, Combinatorica 25, pp.143-186, 2005.

M. Chudnovsky, *. , G. Cornuéjols, *. , X. Liu et al., Recognizing berge graphs, Combinatorica 25, vol.2, pp.143-186, 2005.

S. Cicerone and G. D. Stefano, One the extension of bipartite to parity graphs, Discrete Applied Mathematics, vol.95, pp.181-195, 1999.

N. Brent, C. J. Clark, D. S. Colbourn, and . Johnson, Unit disk graphs, Discrete Mathematics, vol.86, pp.165-177, 1990.

M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vu?kovi?, Balanced 0,±1 matrices I. decomposition, Journal of Combinatorial Theory, Series B, vol.81, pp.243-274, 2001.

M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vu?kovi?, Balanced 0,±1 matrices II. recognition algorithm, Journal of Combinatorial Theory, Series B, vol.81, pp.275-306, 2001.

M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vu?kovi?, Even and odd holes in cap-free graphs, Journal of Graph Theory, vol.30, pp.289-308, 1999.

M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vu?kovi?, Even-holefree graphs part I: Decomposition theorem, Journal of Graph Theory, vol.39, pp.6-49, 2002.

M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vu?kovi?, Even-holefree graphs part II: Recognition algorithm, Journal of Graph Theory, vol.40, pp.238-266, 2002.

M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vu?kovi?, Universally signable graphs, Combinatorica 17, vol.1, pp.67-77, 1997.

M. Conforti, G. Cornuéjols, and M. R. Rao, Decomposition of balanced matrices, Journal of Combinatorial Theory, Series B, vol.77, pp.292-406, 1999.

M. Conforti, G. Cornuéjols, and K. Vu?kovi?, Decomposition of oddhole-free graphs by double star cutsets and 2-joins, Discrete applied mathematics, vol.141, pp.41-91, 2004.

M. Conforti, G. Cornuéjols, and K. Vu?kovi?, Square-free perfect graphs, Journal of Combinatorial Theory, Series B, vol.90, pp.257-307, 2004.

D. Corneil, B. Dalton, and M. Habib, LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs, SIAM Journal on Computing, vol.42, pp.792-807, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00936300

D. Corneil, J. Dusart, M. Habib, and E. Köhler, On the Power of Graph Searching for Cocomparability Graphs, SIAM Journal on Discrete Mathematics, vol.30, pp.569-591, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01273687

D. G. Corneil, H. Lerchs, and L. S. Burlingham, Complement reducible graphs, Discrete Applied Mathematics, vol.3, issue.3, pp.163-174, 1981.

D. G. Corneil, A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs, Discrete Applied Mathematics, vol.138, pp.371-379, 2004.

D. G. Corneil, S. Olariu, and L. Stewart, The LBFS Structure and Recognition of Interval Graphs, vol.23, pp.1905-1953, 2009.

D. G. Corneil and J. Stacho, Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number, Journal of Graph Theory, vol.78, pp.61-79, 2015.

E. Derek-g-corneil, J. Köhler, and . Lanlignel, On end-vertices of lexicographic breadth first searches, Discrete Applied Mathematics, vol.158, pp.434-443, 2010.

G. Derek, R. Corneil, and . Krueger, A unified view of graph searching, SIAM Journal on Discrete Mathematics, vol.22, pp.1259-1276, 2008.

G. Cornuéjols and W. H. Cunningham, Compositions for perfect graphs, Discrete Mathematics, vol.55, pp.245-254, 1985.

A. Cournier and M. Habib, A new linear algorithm for modular decomposition, Trees in algebra and programming (CAAP 94), vol.787, pp.68-84, 1994.

H. Perret-du-cray and I. Sau, Improved FPT algorithms for weighted independent set in bull-free graphs, Discrete Mathematics, vol.341, pp.451-462, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01733496

H. William and . Cunningham, Decomposition of directed graphs, SIAM Journal on Algebraic and Discrete Methods, vol.3, pp.214-228, 1982.

D. Murilo, K. Silva, and . Vu?kovi?, Decomposition of even-hole-free graphs with star cutsets and 2-joins, Journal of Combinatorial Theory, Series B, vol.103, pp.144-183, 2013.

D. Murilo, K. Silva, and . Vu?kovi?, Triangulated neighborhoods in even-holefree graphs, Discrete Mathematics, vol.307, pp.1065-1073, 2007.

K. Dabrowski, Structural Solutions to Maximum Independent Set and Related Problems, 2012.

K. Dabrowski, V. V. Lozin, H. Müller, and D. Rautenbach, Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number, J. Discrete Algorithms, vol.14, pp.207-213, 2012.

E. Dahlhaus, Efficient Parallel and Linear Time Sequential Split Decomposition (Extended Abstract), Proceedings of the 14th Conference on Foundations of Software Technology and Theoretical Computer Science, pp.171-180, 1994.

E. Dahlhaus, Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition, J. Algorithms, vol.36, issue.2, pp.205-240, 2000.

E. Dahlhaus, Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition, Journal of Algorithms, vol.36, pp.205-240, 2000.

L. Danzer, Zur Lösung des Gallaischen Problems über Kreisscheiben in der Euklidischen Ebene, vol.21, pp.111-134, 1986.

D. Défossez, Clique-coloring some classes of odd-hole-free graphs, Journal of Graph Theory, vol.53, issue.3, pp.233-249, 2006.

B. Descartes, Solution to Advanced Problem No. 4526, Amer. Math. Monthly, vol.61, p.352, 1954.

R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Texts in Computer Science, 2013.

F. Dross and F. Havet, On the unavoidability of oriented trees, 2018.
URL : https://hal.archives-ouvertes.fr/hal-02350215

D. Duffus, M. Ginn, and V. Rödl, On the Computational Complexity of Ordered Subgraph Recognition, Random Struct. Algorithms, vol.7, pp.223-268, 1995.

D. Duffus, B. Sands, N. Sauer, and R. E. Woodrow, Two-colouring all two-element maximal antichains, Journal of Combinatorial Theory, Series A, vol.57, issue.1, pp.109-116, 1991.

J. Dusart and M. Habib, A new LBFS-based algorithm for cocomparability graph recognition, Discrete Applied Mathematics, vol.216, pp.149-161, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01274023

P. Erdos, Graph theory and probability, In: canad. J. Math, vol.11, pp.34-38, 1959.

P. Erdös, Problems and results in number theory, Proc. Ninth Manitoba Conference on Numerical Math. and Computing, pp.3-21, 1979.

P. Erdos, W. Adolph, L. Goodman, and . Pósa, The representation of a graph by set intersections, Canad. J. Math, vol.18, p.86, 1966.

T. Erlebach, K. Jansen, and E. Seidel, Polynomial-Time Approximation Schemes for Geometric Intersection Graphs, In: SIAM J. Comput, vol.34, pp.1302-1323, 2005.

G. Even, Z. Lotker, D. Ron, and S. Smorodinsky, Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks, SIAM Journal on Computing, vol.33, pp.94-136, 2003.

S. Even and A. Itai, Queues, stacks, and graphs, Theory of Machines and Computations, pp.71-86, 1971.

Y. Faenza, G. Oriolo, and G. Stauffer, An algorithmic decomposition of claw-free graphs leading to an O (n 3)-algorithm for the weighted stable set problem, Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp.630-646, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00463671

M. Farber, On diameters and radii of bridged graphs, Discrete Mathematics, vol.73, pp.249-260, 1989.

L. Feuilloley and M. Habib, Graph classes and forbidden patterns on three vertices, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01958194

J. Fiala, M. Kami?ski, B. Lidick?, and D. Paulusma, The k-in-a-path problem for claw-free graphs, Algorithmica 62, vol.1, pp.499-519, 2012.
URL : https://hal.archives-ouvertes.fr/inria-00455353

A. V. Fishkin, Disk Graphs: A Short Survey, Approximation and Online Algorithms, First International Workshop, WAOA 2003, vol.2909, pp.260-264, 2003.

P. Csaba, W. Gabor, K. J. Hsu, and . Supowit, Recognizing circle graphs in polynomial time, Journal of ACM, vol.36, pp.435-473, 1989.

T. Gallai, On directed paths and circuits, Theory of graphs, pp.115-118, 1968.

C. Gavoille and C. Paul, Distance labeling scheme and split decomposition, Discrete Mathematics, vol.273, pp.115-130, 2003.
URL : https://hal.archives-ouvertes.fr/hal-00307384

A. Ghouilà-houri, Characterization of nonoriented graphs whose edges can be oriented in such a way as to obtain the graph of an order relation, CR Acad. Sci, vol.254, pp.1370-1371, 1962.

M. Gibson and I. A. Pirwani, Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier -(Extended Abstract, Algorithms -ESA 2010, 18th Annual European Symposium, pp.243-254, 2010.

E. Gioan and C. Paul, Dynamic Distance Hereditary Graphs Using Split Decomposition, Algorithms and Computation, 18th International Symposium (ISAAC, pp.41-51, 2007.
URL : https://hal.archives-ouvertes.fr/lirmm-00189506

E. Gioan, C. Paul, M. Tedder, and D. Corneil, Practical and efficient circle graph recognition, Algorithmica 69, vol.4, pp.759-788, 2014.
URL : https://hal.archives-ouvertes.fr/lirmm-00805194

E. Gioan, C. Paul, M. Tedder, and D. Corneil, Practical and Efficient Split Decomposition via Graph-Labelled Trees, Algorithmica 69, vol.4, pp.789-843, 2014.
URL : https://hal.archives-ouvertes.fr/lirmm-00805193

N. Golowich, Acyclic Colorings and Subgraphs of Directed Graphs, 2014.

M. Charles and G. , Algorithmic graph theory and perfect graphs, Annals of Discrete Mathematics. Second, vol.57, p.314, 2004.

A. Gräf, M. Stumpf, and G. Weißenfels, On coloring unit disk graphs, Algorithmica 20, vol.3, pp.277-293, 1998.

C. Sylvain-gravier, F. Hoàng, and . Maffray, Coloring the hypergraph of maximal cliques of a graph with no long path, Discrete mathematics 272, vol.2, pp.285-290, 2003.

M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 1988.

M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1, pp.169-197, 1981.

A. Grzesik, T. Klimosova, M. Pilipczuk, and M. Pilipczuk, Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs, 2017.

A. Gyárfás, On Ramsey covering-numbers, Infinite and Finite Sets, vol.2, pp.801-816, 1975.

A. Gyárfás, Problem 115, Discrete Mathematics, vol.79, pp.109-110, 1990.

A. Gyárfás, Problems from the world surrounding perfect graphs, Applicationes Mathematicae, vol.19, pp.413-441, 1987.

A. Gyárfás, E. Szemerédi, and Z. Tuza, Induced subtrees in graphs of large chromatic number, Discrete Mathematics, vol.30, pp.235-244, 1980.

M. Habib, A. Mamcarz, and F. De-montgolfier, Computing H-joins with application to 2-modular decomposition, Algorithmica 70, pp.245-266, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00921775

M. Habib, R. Mcconnell, C. Paul, and L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, vol.234, pp.59-84, 2000.

M. Habib and L. Mouatadid, Maximum induced matching algorithms via vertex ordering characterizations, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01672520

M. Habib and C. Paul, A survey of the algorithmic aspects of modular decomposition, Computer Science Review, vol.4, issue.1, pp.41-59, 2010.

S. Har-peled, H. Kaplan, W. Mulzer, L. Roditty, P. Seiferth et al., Stabbing pairwise intersecting disks by five points, 2018.

A. Harutyunyan, T. Le, A. Newman, and S. Thomassé, Coloring dense digraphs, Electronic Notes in Discrete Mathematics, vol.61, pp.577-583, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01990330

A. Harutyunyan and B. Mohar, Gallai's theorem for list coloring of digraphs, SIAM Journal on Discrete Mathematics, vol.25, pp.170-180, 2011.

A. Harutyunyan and B. Mohar, Planar digraphs of digirth five are 2-colorable, Journal of Graph Theory, vol.84, pp.408-427, 2017.

A. Harutyunyan and B. Mohar, Strengthened Brooks' theorem for digraphs of girth at least three, In: the electronic journal of combinatorics, vol.18, p.195, 2011.

A. Harutyunyan and B. Mohar, Two results on the digraph chromatic number, Discrete Mathematics, vol.312, pp.1823-1826, 2012.

M. Hasse, Zur algebraischen begründung der graphentheorie. i, Mathematische Nachrichten, vol.28, pp.275-290, 1965.

D. Haussler and E. Welzl, Epsilon-Nets and Simplex Range Queries, pp.61-71, 1986.

P. Hell, B. Mohar, and A. Rafiey, Ordering without Forbidden Patterns, Algorithms -ESA 2014 -22th Annual European Symposium, Wroclaw, Poland, September 8-10, pp.554-565, 2014.

P. Hlin?ný and J. Kratochvíl, Representing graphs by disks and balls (a survey of recognition-complexity results), Discrete Mathematics, vol.229, pp.101-124, 2001.

D. S. Hochbaum and W. Maass, Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI, J. ACM, vol.32, issue.1, pp.130-136, 1985.

I. Holyer, The NP-Completeness of Edge-Colouring, 1981.

W. Hsu and R. M. Mcconnell, PC-trees and circular-ones arrangements, Theoretical Computer Science, vol.296, pp.99-116, 2003.

R. Javadi and S. Hajebi, Edge clique cover of claw-free graphs

G. Kalai and R. Meshulam,

J. Ross, T. Kang, and . Müller, Sphere and Dot Product Representations of Graphs, Discrete & Computational Geometry, vol.47, issue.3, pp.548-568, 2012.

T. Karthick, Independent Sets in Some Classes of S i,j,k -free Graphs, J. Comb. Optim, vol.34, issue.2, pp.612-630, 2017.

T. Karthick and F. Maffray, Maximum weight independent sets in classes related to claw-free graphs, Discrete Applied Mathematics, vol.216, pp.233-239, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01437504

A. Hal, V. Kierstead, and . Rodl, Applications of hypergraph coloring to coloring graphs not inducing certain trees, Discrete Mathematics, vol.150, pp.187-193, 1996.

A. Hal, W. Kierstead, and . Trotter, Colorful induced subgraphs, Discrete mathematics, vol.101, pp.165-169, 1992.

A. Hal, Y. Kierstead, and . Zhu, Radius three trees in graphs with large chromatic number, SIAM Journal on Discrete Mathematics, vol.17, pp.571-581, 2004.

A. Henry, . Kierstead, and . Stephen-g-penrice, Radius two trees specify ?-bounded classes, Journal of Graph Theory, vol.18, pp.119-129, 1994.

A. King and C. Graphs, Two Conjectures on ?, 2009.

P. Koebe, Kontaktprobleme der konformen Abbildung, Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig, vol.88, pp.141-164, 1936.

E. Köhler and L. Mouatadid, Linear Time LexDFS on Cocomparability Graphs, Algorithm Theory -SWAT, pp.319-330, 2014.

D. Kühn and D. Osthus, Induced subdivisions in K s, s-free graphs of large average degree, Combinatorica 24, vol.2, pp.287-304, 2004.

E. Jan-van-leeuwen, Better Approximation Schemes for Disk Graphs, Algorithm Theory -SWAT 2006, 10th ScandinavianWorkshop on Algorithm Theory, pp.316-327, 2006.

C. Lekkeikerker and . Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, vol.51, pp.45-64, 1962.

B. Lévêque, F. Maffray, and M. Preissmann, Characterizing path graphs by forbidden induced subgraphs, Journal of Graph Theory, vol.62, pp.369-384, 2009.

D. Lokshtanov, M. Vatshelle, and Y. Villanger, Independent Set in P 5 -Free Graphs in Polynomial Time, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.570-581, 2014.

L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics, vol.2, pp.253-267, 1972.

T. Ma and J. Spinrad, An O (n2) algorithm for undirected split decomposition, Journal of Algorithms, vol.16, pp.145-160, 1994.

F. Maffray and M. Preissmann, On the NP-completeness of the k-colorability problem for triangle-free graphs, Discrete Mathematics, vol.162, pp.313-317, 1996.

F. Maffray, N. Trotignon, and K. Vu?kovi?, Algorithms for square-3PC ( , )-free Berge graphs, SIAM Journal on Discrete Mathematics, vol.22, pp.51-71, 2008.
URL : https://hal.archives-ouvertes.fr/halshs-00130439

D. Marx and M. Pilipczuk, Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams, Algorithms -ESA, 2015.

R. M. Mcconnell, A certifying algorithm for the consecutive-ones property, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, p.777, 2004.

M. Ross, J. P. Mcconnell, and . Spinrad, Linear-time modular decomposition and efficient transitive orientation of comparability graphs, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.536-545, 1994.

A. Terry, F. R. Mckee, and . Mcmorris, Topics in intersection graph theory, 1999.

G. Mertzios and D. Corneil, A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs, SIAM Journal on Discrete Mathematics, vol.26, pp.940-963, 2012.

B. Mohar, Choosability for the circular chromatic number, 2003.

B. Mohar, Eigenvalues and colorings of digraphs, Linear Algebra and its Applications, vol.432, pp.2273-2277, 2010.

B. Mohar and R. Skrekovski, The Grötzsch theorem for the hypergraph of maximal cliques, Electron. J. Combin, vol.6, p.128, 1999.

B. Mohar and H. Wu, Dichromatic Number And Fractional Chromatic Number". In: Forum of Mathematics, vol.4, p.32, 2016.

H. Rolf and . Möhring, Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions, Annals of Operations Research, vol.6, pp.195-225, 1985.

H. Rolf, F. Möhring, and . Radermacher, Substitution decomposition for discrete structures and connections with combinatorial optimization, Annals of Discrete Mathematics, vol.19, pp.257-356, 1984.

J. Mycielski, Sur le coloriage des graphes, Colloq. Math, vol.3, p.9, 1955.

W. Naji, Reconnaissance des graphes de cordes, Discrete mathematics, vol.54, pp.329-337, 1985.

V. Neumann-lara, The dichromatic number of a digraph, In: Journal of Combinatorial Theory, Series B, vol.33, pp.265-270, 1982.

V. Neumann-lara, Vertex colourings in digraphs, Some Problems. Seminar notes, 1985.

T. Nieberg and J. Hurink, A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs, Approximation and Online Algorithms, Third International Workshop, WAOA 2005, pp.296-306, 2005.

T. Nieberg, J. Hurink, and W. Kern, A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs, Graph-Theoretic Concepts in Computer Science, 30th International Workshop, pp.214-221, 2004.

S. Olariu, An Optimal Greedy Heuristic to Color Interval Graphs, In: Inf. Process. Lett, vol.37, pp.21-25, 1991.

S. Oum, Rank-width: Algorithmic and structural results, Discrete Applied Mathematics, vol.231, pp.15-24, 2017.

C. Paul, Algorithmic aspects of modular decomposition, Habilitation à diriger des recherches. Université Montpellier II -Sciences et Techniques du Languedoc, 2006.
URL : https://hal.archives-ouvertes.fr/lirmm-00533514

I. Penev, Perfect Graphs with No Balanced Skew-Partition Are 2-Clique-Colorable, J. Graph Theory, vol.81, pp.213-235, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01995388

S. Poljak, A note on stable sets and colorings of graphs, Commentationes Mathematicae Universitatis Carolinae, vol.15, pp.307-309, 1974.

V. Raghavan and J. P. Spinrad, Robust algorithms for restricted domains, J. Algorithms, vol.48, pp.160-172, 2003.

G. Ramalingam and C. P. Rangan, A unified approach to domination problems on interval graphs, Information Processing Letters, vol.27, pp.271-274, 1988.

M. Rao, Coloring a Graph Using Split Decomposition, Graph-Theoretic Concepts in Computer Science (WG), vol.3353, pp.129-141, 2004.

M. Rao, Solving some NP-complete problems using split decomposition, Discrete Applied Mathematics, vol.156, pp.2768-2780, 2008.
URL : https://hal.archives-ouvertes.fr/lirmm-00324549

V. Rödl, On the chromatic number of subgraphs of a given graph, Proceedings of the, vol.64, pp.370-371, 1977.

D. J. Rose, R. E. Tarjan, and G. S. Lueker, Algorithmic Aspects of Vertex Elimination on Graphs, SIAM Journal on Computing, vol.5, pp.266-283, 1976.

B. Roy, Nombre chromatique et plus longs chemins d'un graphe, Revue française d'informatique et de recherche opérationnelle, vol.1, pp.129-132, 1967.

A. Scott, Induced trees in graphs of large chromatic number, Journal of Graph Theory, vol.24, pp.297-311, 1997.

A. Scott and P. Seymour, A survey of ?-boundedness, 2018.

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. I. Odd holes, Journal of Combinatorial Theory, Series B, vol.121, pp.68-84, 2016.

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes, 2015.

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. IX. Rainbow paths, 2017.

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. IX. Rainbow paths, 2017.

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. VI. Banana trees, 2017.

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture, 2017.

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue, 2017.

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. XIII. New brooms". In: arXiv preprint, 2018.

K. Simon, A new simple linear algorithm to recognize interval graphs, Workshop on Computational Geometry, pp.289-308, 1991.

D. Warren, N. C. Smith, and . Wormald, Geometric Separator Theorems & Applications, 39th Annual Symposium on Foundations of Computer Science, FOCS '98, pp.232-243, 1998.

C. R. Frits and . Spieksma, Approximating an interval scheduling problem". In: Approximation Algorithms for Combinatiorial Optimization, pp.169-180, 1998.

J. P. Spinrad, Recognition of Circle Graphs, Journal of Algorithms, vol.16, pp.264-282, 1994.

J. Stacho,

L. Stachó, A solution of Gallai's problem on pinning down circles, In: Mat. Lapok, vol.32, pp.19-47, 1981.

P. David and . Sumner, Subtrees of a graph and chromatic number, The theory and applications of graphs, pp.557-576, 1981.

N. Stéphan-thomassé, K. Trotignon, and . Vu?kovi?, A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs, Algorithmica 77, vol.3, pp.619-641, 2017.

N. Trotignon, Decomposing Berge graphs and detecting balanced skew partitions, Journal of Combinatorial Theory, Series B, vol.98, issue.1, pp.173-225, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00265245

N. Trotignon, Perfect graphs: a survey, 2013.

N. Trotignon, Personal Communication, 2018.

N. Trotignon and K. Vu?kovi?, Combinatorial optimization with 2-joins, Journal of Combinatorial Theory, Series B, vol.102, issue.1, pp.153-185, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00800197

K. Truemper, Alpha-balanced graphs and matrices and GF (3)-representability of matroids, Journal of Combinatorial Theory, Series B, vol.32, pp.112-139, 1982.

N. Vladimir, . Vapnik, and . Ya-chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Measures of complexity, pp.11-30, 2015.

B. Verweij and K. Aardal, An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling, Algorithms -ESA' 99, pp.426-437, 1999.

. Lm and . Vitaver, Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix, Dokl. Akad. Nauk SSSR, vol.147, p.728, 1962.

K. Vu?kovi?, Even-hole-free graphs: a survey, Applicable Analysis and Discrete Mathematics, pp.219-240, 2010.

K. Vu?kovi?, The world of hereditary graph classes viewed through Truemper configurations, Surveys in Combinatorics, vol.409, p.265, 2013.

W. J. Kolen-antoon, J. Lenstra, P. Karel, H. Christos, S. Frits et al., Interval scheduling: A survey, Naval Research Logistics (NRL), vol.54, pp.530-543, 2007.

D. R. Wood, Characterisations of Intersection Graphs by Vertex Orderings, 2004.

M. Wrochna, Personal Communication, 2018.

D. Zuckerman, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number, Theory of Computing, vol.3, pp.103-128, 2007.

A. Zykov, On some properties of linear complexes, Matematicheskii sbornik, vol.66, pp.163-188, 1949.