N. Alon, Testing subgraphs in large graphs. Random Struct, Algorithms, vol.21, p.359370, 2002.

W. Noga-alon, . Fernandez-de-la, R. Vega, M. Kannan, and . Karpinski, Random sampling and approximation of max-csps, J. Comput. Syst. Sci, vol.67, p.212243, 2003.

E. Noga-alon, M. Fischer, M. Krivelevich, and . Szegedy, Ecient testing of large graphs, Combinatorica, vol.20, p.451476, 2000.

E. Noga-alon, I. Fischer, A. Newman, and . Shapira, A combinatorial characterization of the testable graph properties : It's all about regularity, SIAM Journal on Computing, vol.39, issue.1, p.143167, 2009.

N. Alon and M. Krivelevich, -colorability, SIAM Journal on Discrete Mathematics, vol.15, issue.2, p.211227, 2002.
DOI : 10.1137/S0895480199358655

URL : https://hal.archives-ouvertes.fr/halshs-00480214

N. Alon and A. Shapira, A characterization of the (natural) graph properties testable with one-sided error, Proc. of FOCS 2005, p.429438, 2005.

N. Alon and A. Shapira, Every monotone graph property is testable, SIAM Journal on Computing, vol.38, issue.2, p.505522, 2008.
DOI : 10.1145/1060590.1060611

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

G. Andersson and L. Engebretsen, Property testers for dense constraint satisfaction programs on nite domains, Random Struct. Algorithms, vol.21, p.1432, 2002.
DOI : 10.1002/rsa.10041

J. Baget, Représenter des connaissances et raissonner avec des hypergraphes : de la projection à la dérivation sous contraintes, 2001.

J. Baget, Homomorphismes d'hypergraphes pour la subsomption en rdf/rdfs. L'OBJET, p.203216, 2004.
DOI : 10.3166/objet.10.2-3.203-216

URL : https://hal.archives-ouvertes.fr/hal-00906633

F. Behrend, On the sets of integers which contain no three in arithmetic progression, Proceedings of the National Academy of Sciences 23, p.331332, 1946.

I. Ben-eliezer, T. Kaufman, M. Krivelevich, and D. Ron, Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.12131222, 2008.
DOI : 10.1137/S0097539793255151

A. Coja-oghlan, C. Cooper, and A. Frieze, An ecient sparse regularity concept, SIAM Journal on Discrete Mathematics, vol.23, issue.4, 2010.
DOI : 10.1137/080730160

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

O. Goldreich, Introduction to testing graph properties, Electronic Colloquim on Computational Complexity, 2010.

W. T. Gowers, Lower bounds of tower type for szemerédi's uniformity lemma. Geometric And Functional Analysis, p.322337, 1997.

P. Hell and J. Nesetril, Graphs and Homomorphisms, 2005.
DOI : 10.1093/acprof:oso/9780198528173.001.0001

M. Chein and M. Mugnier, Graph-Based Knowledge Representation : Computational Foundations of Conceptual Graphs. Advanced Information and Knowledge Processing, 2008.
URL : https://hal.archives-ouvertes.fr/lirmm-00355336

V. Rodl and M. Schacht, Generalizations of the removal lemma, Combinatorica, vol.113, issue.7, p.467501, 2009.
DOI : 10.1007/s00493-009-2320-x

D. Ron, Algorithmic and analysis techniques in property testing. Found. Trends Theor, Comput. Sci, vol.5, issue.2, p.73205, 2010.

E. Satu and . Schaeer, Scalable uniform graph sampling by local computation, SIAM J. Scientic Computing, vol.32, issue.5, p.29372963, 2010.

F. John and . Sowa, Conceptual graphs for a data base interface, IBM J. Res. Dev, vol.20, p.336357, 1976.

R. Williams, A new algorithm for optimal 2-constraint satisfaction and its implications, Theor. Comput. Sci, vol.348, issue.2, p.357365, 2005.