S. Arora, D. Karger, and M. Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pp.284-293, 1995.

J. Bermond, B. Jackson, and F. Jaeger, Shortest coverings of graphs with cycles, Journal of Combinatorial Theory, Series B, vol.35, issue.3, pp.297-308, 1983.
DOI : 10.1016/0095-8956(83)90056-4

B. Bollobás and I. Leader, Set systems with few disjoint pairs, pp.559-570, 2003.

A. Coja-oghlan, The Lov??sz Number of Random Graphs, Combinatorics, Probability and Computing, vol.14, issue.4, pp.439-465, 2005.
DOI : 10.1017/S0963548305006826

M. Devos, High-girth cubic graphs are homomorphic to the Clebsch graph, Journal of Graph Theory, vol.14, issue.6, pp.241-259, 2011.
DOI : 10.1002/jgt.20580

M. Devos, J. Ne?et?il, and A. Raspaud, On edge-maps whose inverse preserves flows and tensions, Graph Theory in Paris: Proceedings of a Conference in Memory, Trends in Mathematics, 2006.

J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, vol.69, issue.1 and 2, pp.125-130, 1965.
DOI : 10.6028/jres.069B.013

R. Engström, T. Färnqvist, P. Jonsson, and J. Thapper, An approximability-related parameter on graphs?properties and applications, Discr. Math. Th. Comp. Sc, vol.17, issue.1, pp.33-66, 2015.

P. Erd? and O. , Graph theory and probability, Canad, J. Math, vol.11, pp.34-38, 1959.

G. Fan, Minimum cycle covers of graphs, Journal of Graph Theory, vol.25, issue.3, pp.229-242, 1997.
DOI : 10.1002/(SICI)1097-0118(199707)25:3<229::AID-JGT6>3.0.CO;2-N

U. Feige, M. Langberg, and G. Schechtman, Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers, SIAM Journal on Computing, vol.33, issue.6, pp.1338-1368, 2004.
DOI : 10.1137/S0097539703431391
URL : http://authors.library.caltech.edu/27189/1/FEIsiamjc04.pdf

W. Fernandez-de, L. Vega, and M. Karpinski, Polynomial time approximation of dense weighted instances of MAX-CUT, Random Structures, Algorithms, vol.16, issue.4, pp.314-332, 2000.

T. Färnqvist, P. Jonsson, and J. Thapper, Approximability distance in the space of Hcolourability problems, Proceedings of the 4th International Computer Science Symposium in Russia, 2009.

C. Godsil, D. Roberson, and B. Rooney, Robert?ámalRobert?Robert?ámal, and Antonios Varvitsiotis, Rigidity and Graph Theory III: Categorical Products and Unique Homomorphisms, in preparation, 2015.

C. Godsil and G. Royle, Algebraic graph theory, Graduate Texts in Mathematics, vol.207, 2001.
DOI : 10.1007/978-1-4613-0163-9

X. Michel, D. P. Goemans, and . Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach, vol.42, issue.6, pp.1115-1145, 1995.

M. Grötschel and W. R. Pulleyblank, Weakly bipartite graphs and the Max-cut problem, Operations Research Letters, vol.1, issue.1, pp.23-27, 1981.
DOI : 10.1016/0167-6377(81)90020-1

W. Imrich and S. Klav?ar, Product graphs, structure and recognition, 2000.

S. Janson, T. ?uczak, and A. Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, 2000.

S. Kale and C. Seshadhri, Combinatorial Approximation Algorithms for MaxCut using Random Walks, Innovations in Computer Science ? ICS, pp.367-388, 2010.

F. Kardo?, D. Král, and J. Volec, Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs, Random Structures & Algorithms, vol.14, issue.4, pp.506-520, 2012.
DOI : 10.1002/rsa.20471

D. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM, vol.45, issue.2, pp.246-265, 1998.
DOI : 10.1145/274787.274791

K. Kawarabayashi and M. Thorup, Coloring 3-colorable graphs with o(n 1/5 ) colors, 31st International Symposium on Theoretical Aspects of Computer Science STACS 2014, pp.458-469, 2014.

L. Lovász, Kneser's conjecture, chromatic number, and homotopy, Journal of Combinatorial Theory, Series A, vol.25, issue.3, pp.319-324, 1978.
DOI : 10.1016/0097-3165(78)90022-5

L. Lovász, Combinatorial problems and exercises, 1979.
DOI : 10.1090/chel/361

J. Ne?et?il, On tension-continuous mappings, European Journal of Combinatorics, vol.29, issue.4, pp.1025-1054, 2008.
DOI : 10.1016/j.ejc.2007.11.023

S. Poljak and Z. Tuza, Maximum bipartite subgraphs of Kneser graphs, Graphs Combin, pp.191-199, 1987.

H. Jack, R. M. Van-lint, and . Wilson, A course in combinatorics, 2001.