A. Berman and X. Zhang, Bipartite density of cubic graphs, Discrete Mathematics, vol.260, issue.1-3, pp.27-35, 2003.
DOI : 10.1016/S0012-365X(02)00490-9

B. Bollobás and P. Erd?-os, Cliques in random graphs, Mathematical Proceedings of the Cambridge Philosophical Society, vol.77, issue.03, pp.419-427, 1976.
DOI : 10.1017/S0305004100053056

J. A. Bondy and S. C. Locke, Largest bipartite subgraphs in triangle-free graphs with maximum degree three, Journal of Graph Theory, vol.10, issue.4, pp.477-504, 1986.
DOI : 10.1002/jgt.3190100407

O. V. Borodin, S. Kim, A. V. Kostochka, and D. B. West, Homomorphisms from sparse graphs with large girth, Journal of Combinatorial Theory, Series B, vol.90, issue.1, pp.147-159, 2004.
DOI : 10.1016/S0095-8956(03)00081-9

A. Coja-oghlan, C. Moore, and V. Sanwalani, MAX k-CUT and approximating the chromatic number of random graphs. Random Structures and Algorithms, pp.289-322, 2005.

. Crescenzi, A short guide to approximation preserving reductions, Proceedings of Computational Complexity. Twelfth Annual IEEE Conference, pp.262-273, 1997.
DOI : 10.1109/CCC.1997.612321

R. Crowston, M. Jones, and M. Mnich, Max-Cut parameterized above the Edwards-Erd? os bound, 2011.

E. De-klerk, D. V. Pasechnik, and J. P. Warners, On Approximate Graph Colouring and MAX-k-CUT Algorithms Based on the ??-Function, Journal of Combinatorial Optimization, vol.8, issue.3, pp.267-294, 2004.
DOI : 10.1023/B:JOCO.0000038911.67280.3f

R. D. Dutton and R. C. Brigham, Edges in graphs with large girth, Graphs and Combinatorics, vol.48, issue.4, pp.315-321, 1991.
DOI : 10.1007/BF01787638

Z. Dvo?ák, R. ?krekovski, and T. Valla, Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph, SIAM Journal on Discrete Mathematics, vol.22, issue.2, pp.568-591, 2008.
DOI : 10.1137/060650507

R. Engström, T. Färnqvist, P. Jonsson, and J. Thapper, Graph homomorphisms, circular colouring, and fractional covering by H-cuts, 2009.

R. Engström, T. Färnqvist, P. Jonsson, and J. Thapper, Properties of an Approximability-related Parameter on Circular Complete Graphs, Proceedings of the 5th Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS-2009), pp.115-120, 2009.
DOI : 10.1016/j.endm.2009.11.020

P. Erd?-os and A. Rényi, On the evolution of random graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences, pp.17-61, 1960.

A. Frieze and M. Jerrum, Improved approximation algorithms for MAX k-CUT and MAX BISECTION, Algorithmica, vol.18, issue.1, pp.67-81, 1997.
DOI : 10.1007/3-540-59408-6_37

T. Färnqvist, P. Jonsson, and J. Thapper, Approximability Distance in the Space of H-Colourability Problems, Proceedings of the 4th International Computer Science Symposium in Russia, pp.92-104, 2009.
DOI : 10.1007/BF01375472

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

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, vol.42, issue.6, pp.1115-1145, 1995.
DOI : 10.1145/227683.227684

P. Hell and J. Ne?et?il, Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications, 2004.

P. Hell and J. Ne?et?il, On the complexity of H-coloring, Journal of Combinatorial Theory, Series B, vol.48, issue.1, pp.92-110, 1990.
DOI : 10.1016/0095-8956(90)90132-J

G. Hopkins and W. Staton, Extremal bipartite subgraphs of cubic triangle-free graphs, Journal of Graph Theory, vol.10, issue.2, pp.115-121, 1982.
DOI : 10.1002/jgt.3190060205

J. Håstad, Some optimal inapproximability results, Journal of the ACM, vol.48, issue.4, pp.798-869, 2001.
DOI : 10.1145/502090.502098

J. Håstad, Every 2-CSP allows nontrivial approximation, Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC-2005), pp.740-746, 2005.

M. Isaksson and E. Mossel, Maximally stable Gaussian partitions with discrete applications. arXiv:0903.3362v3 [math

. Jaeger, Nowhere-zero flow problems, pp.71-95, 1988.

P. Jonsson, A. Krokhin, and F. Kuivinen, Hard constraint satisfaction problems have hard gaps at location 1, Theoretical Computer Science, vol.410, issue.38-40, pp.38-403856, 2009.
DOI : 10.1016/j.tcs.2009.05.022
URL : http://doi.org/10.1016/j.tcs.2009.05.022

V. Kann, S. Khanna, J. Lagergren, and A. Panconesi, On the hardness of approximating MAX k-CUT and its dual, Chicago Journal of Theoretical Computer Science, issue.2, 1997.

A. C. Kaporis, L. M. Kirousis, and E. C. Stavropoulos, Approximating Almost All Instances of Max-Cut Within a Ratio Above the H??stad Threshold, Proceedings of the 14th Annual European Symposium on Algorithms (ESA- 2006), pp.432-443, 2006.
DOI : 10.1007/11841036_40

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, pp.85-103, 1972.
DOI : 10.1007/978-3-540-68279-0_8

S. Khot, On the power of unique 2-prover 1-round games, Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC-2002), pp.767-775, 2002.

S. Khot, G. Kindler, E. Mossel, and R. , Optimal Inapproximability Results for MAX???CUT and Other 2???Variable CSPs?, SIAM Journal on Computing, vol.37, issue.1, pp.319-357, 2007.
DOI : 10.1137/S0097539705447372

J. Kim and R. Williams, Improved parameterized algorithms for constraint satisfaction, Proceedings of the 6th International Symposium on Parameterized and Exact Computation, 2011.
URL : https://hal.archives-ouvertes.fr/hal-01496463

H. Lai and B. Liu, Graph homomorphism into an odd cycle, Bulletin of the Institute of Combinatorics and its Applications, pp.19-24, 2000.

S. C. Locke, A note on bipartite subgraphs of triangle-free regular graphs, Journal of Graph Theory, vol.6, issue.2, pp.181-185, 1990.
DOI : 10.1002/jgt.3190140206

D. W. Matula, The employee party problem, Notices of the American Mathematical Society, vol.19, p.382, 1972.

Z. Pan and X. Zhu, The circular chromatic number of series-parallel graphs of large odd girth, Discrete Mathematics, vol.245, issue.1-3, pp.235-246, 2002.
DOI : 10.1016/S0012-365X(01)00144-3

P. Raghavendra, Optimal algorithms and inapproximability results for every CSP?, Proceedings of the fourtieth annual ACM symposium on Theory of computing, STOC 08, pp.245-254, 2008.
DOI : 10.1145/1374376.1374414
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.173.1202

P. Raghavendra and D. Steurer, How to Round Any CSP, 2009 50th Annual IEEE Symposium on Foundations of Computer Science, 2009.
DOI : 10.1109/FOCS.2009.74

S. Sahni and T. Gonzalez, P-Complete Approximation Problems, Journal of the ACM, vol.23, issue.3, pp.555-565, 1976.
DOI : 10.1145/321958.321975

H. U. Simon, Continuous reductions among combinatorial optimization problems, Acta Informatica, vol.49, issue.8, pp.771-785, 1989.
DOI : 10.1007/BF00289161

J. Soto, Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning, SIAM Journal on Discrete Mathematics, vol.29, issue.1, 2009.
DOI : 10.1137/14099098X

L. Trevisan, Max cut and the smallest eigenvalue, Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC-2009), pp.263-272, 2009.

P. Turán, On an extremal problem in graph theory, Matematicko Fizicki Lapok, vol.48, pp.436-452, 1941.

. Zhu, Circular chromatic number, Discrete Mathematics, vol.229, issue.1-3, pp.371-410, 2001.
DOI : 10.1016/S0012-365X(00)00217-X
URL : https://hal.archives-ouvertes.fr/hal-00307764