V. E. Alekseev, On the number of maximal independent sets in graphs from hereditary classes. Combinatorial-algebraic methods in discrete optimization, pp.5-8, 1991.

N. Alon, Neighborly Families of Boxes and Bipartite Coverings, Algorithms and Combinatorics, vol.14, pp.27-31, 1997.
DOI : 10.1007/978-3-642-60406-5_3

K. Amano, Some improved bounds on communication complexity via new decomposition of cliques, Discrete Applied Mathematics, vol.166, 2012.
DOI : 10.1016/j.dam.2013.09.015

B. Bollobas, Random Graphs, 2001.
URL : https://hal.archives-ouvertes.fr/hal-00914127

N. Bousquet, A. Lagoutte, and S. Thomassé, The Erd??s???Hajnal conjecture for paths and antipaths, Journal of Combinatorial Theory, Series B, vol.113, 2013.
DOI : 10.1016/j.jctb.2015.01.001

K. Cameron, E. M. Eschen, C. T. Hoàng, and R. Sritharan, The Complexity of the List Partition Problem for Graphs, SIAM Journal on Discrete Mathematics, vol.21, issue.4, pp.900-929, 2007.
DOI : 10.1137/060666238

S. M. Cioab? and M. Tait, Variations on a theme of Graham and Pollak, Discrete Mathematics, vol.313, issue.5, pp.665-676, 2013.
DOI : 10.1016/j.disc.2012.12.001

M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk, The stubborn problem is stubborn no more (a polynomial algorithm for 3???compatible colouring and the stubborn list partition problem), pp.1666-1674, 2011.
DOI : 10.1137/1.9781611973082.128

T. Feder and P. Hell, Full Constraint Satisfaction Problems, SIAM Journal on Computing, vol.36, issue.1, pp.230-246, 2006.
DOI : 10.1137/S0097539703427197
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.123.4068

T. Feder, P. Hell, and J. Huang, Bi-arc graphs and the complexity of list homomorphisms, Journal of Graph Theory, vol.51, issue.1, pp.61-80, 2003.
DOI : 10.1002/jgt.10073

T. Feder, P. Hell, S. Klein, and R. Motwani, List Partitions, SIAM Journal on Discrete Mathematics, vol.16, issue.3, pp.449-478, 2003.
DOI : 10.1137/S0895480100384055

S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. De-wolf, Linear vs. semidefinite extended formulations, Proceedings of the 44th symposium on Theory of Computing, STOC '12, pp.95-106, 2012.
DOI : 10.1145/2213977.2213988

R. L. Graham and H. O. Pollak, On embedding graphs in squashed cubes. Graph theory and applications, pp.99-110, 1972.

D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Proceedings of the second annual symposium on Computational geometry , SCG '86, pp.61-71, 1986.
DOI : 10.1145/10515.10522

H. Huang and B. Sudakov, A counterexample to the Alon-Saks-Seymour conjecture and related problems, Combinatorica, vol.8, issue.1, pp.205-219, 2012.
DOI : 10.1007/s00493-012-2746-4

J. Kahn, Recent results on some not-so-recent hypergraph matching and covering problems, Extremal problems for finite sets. Bolyai Society mathematical studies, 1994.

A. V. Kostochka and X. Zhu, Adapted List Coloring of Graphs and Hypergraphs, SIAM Journal on Discrete Mathematics, vol.22, issue.1, pp.398-408, 2008.
DOI : 10.1137/070698385

E. Kushilevitz and N. Nisan, Communication complexity, 1997.

D. Lokshtanov, M. Vatshelle, and Y. Villanger, Independent set in P 5 -free graphs in polynomial time, 2013.

L. Lovász, Communication complexity: a survey, Paths, flows, and VLSI-layout, pp.235-265, 1990.

L. Lovász, Stable sets and polynomials, Discrete Mathematics, vol.124, issue.1-3, pp.137-153, 1994.
DOI : 10.1016/0012-365X(92)00057-X

A. Razborov, The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear, Discrete Mathematics, vol.108, issue.1-3, pp.393-396, 1992.
DOI : 10.1016/0012-365X(92)90691-8

D. G. Schell, Matrix partitions of digraphs, 2009.

H. Tverberg, On the decomposition ofkn into complete bipartite graphs, Journal of Graph Theory, vol.29, issue.4, pp.493-494, 1982.
DOI : 10.1002/jgt.3190060414

V. N. Vapnik, A. Ya, and . Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, pp.264-280, 1971.

M. Yannakakis, Expressing combinatorial optimization problems by Linear Programs, Journal of Computer and System Sciences, vol.43, issue.3, pp.441-466, 1991.
DOI : 10.1016/0022-0000(91)90024-Y

J. Zaks, Bounds of neighborly families of convex polytopes, Geometriae Dedicata, vol.8, issue.3, pp.279-296, 1979.
DOI : 10.1007/BF00151512