{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T20:52:23Z","timestamp":1770324743465,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,6,4]],"date-time":"2008-06-04T00:00:00Z","timestamp":1212537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2010,2]]},"DOI":"10.1007\/s10107-008-0233-x","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T14:31:11Z","timestamp":1212503471000},"page":"249-268","source":"Crossref","is-referenced-by-count":27,"title":["Copositive programming motivated bounds on the stability and the chromatic numbers"],"prefix":"10.1007","volume":"121","author":[{"given":"Igor","family":"Dukanovic","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franz","family":"Rendl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,6,4]]},"reference":[{"key":"233_CR1","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1023\/A:1020209017701","volume":"24","author":"I.M. Bomze","year":"2001","unstructured":"Bomze I.M., de Klerk E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24, 163\u2013185 (2001)","journal-title":"J. Global Optim."},{"key":"233_CR2","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1023\/A:1026583532263","volume":"18","author":"I.M. Bomze","year":"2000","unstructured":"Bomze I.M., D\u00fcr M., de Klerk E., Roos C., Quist A.J., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Global Optim. 18, 301\u2013320 (2000)","journal-title":"J. Global Optim."},{"key":"233_CR3","doi-asserted-by":"crossref","unstructured":"Burer, S.: On the copositive representation of binary and continuos nonconvex quadratic Programs. Working paper (2007)","DOI":"10.1007\/s10107-008-0223-z"},{"issue":"4","key":"233_CR4","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1016\/j.disc.2006.01.004","volume":"306","author":"S. Busygin","year":"2006","unstructured":"Busygin S., Pasechnik D.V.: On NP-hardness of the clique partition\u2014independence number gap recognition and related problems. Discrete Math. 306(4), 460\u2013463 (2006)","journal-title":"Discrete Math."},{"key":"233_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/b105286","volume-title":"Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications","author":"E. Klerk de","year":"2002","unstructured":"de Klerk E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer, Dordrecht (2002)"},{"key":"233_CR6","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E. de Klerk","year":"2002","unstructured":"de Klerk E., Pasechnik D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"issue":"2\u20133","key":"233_CR7","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/s10107-006-0039-7","volume":"109","author":"E. de Klerk","year":"2007","unstructured":"de Klerk E., Pasechnik D.V., Schrijver A.: Reduction of symmetric semidefinite programs using the regular *-representation. Math. Program. 109(2\u20133), 613\u2013624 (2007)","journal-title":"Math. Program."},{"key":"233_CR8","doi-asserted-by":"crossref","unstructured":"Dukanovic, I.: Semidefinite programming applied to graph coloring problem. Ph.D. thesis, University of Klagenfurt, Austria (2008, forthcoming)","DOI":"10.1016\/j.dam.2006.07.014"},{"key":"233_CR9","unstructured":"Dukanovic, I., Rendl, F.: Reductions of group symmetric semidefinite programs. Working paper (2005)"},{"issue":"2","key":"233_CR10","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s10107-006-0026-z","volume":"109","author":"I. Dukanovic","year":"2007","unstructured":"Dukanovic I., Rendl F.: Semidefinite programming relaxations for graph coloring and maximal clique problems. Math. Program. B 109(2), 345\u2013366 (2007)","journal-title":"Math. Program. B"},{"key":"233_CR11","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.jpaa.2003.12.011","volume":"192","author":"K. Gatermann","year":"2004","unstructured":"Gatermann K., Parrilo P.A.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192, 95\u2013128 (2004)","journal-title":"J. Pure Appl. Algebra"},{"key":"233_CR12","unstructured":"Gvozdenovi\u0107, N., Laurent, M.: Personal communication (2005)"},{"key":"233_CR13","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/11496915_11","volume":"3509","author":"N. Gvozdenovi\u0107","year":"2005","unstructured":"Gvozdenovi\u0107 N., Laurent M.: Semidefinite bounds for the stability number of a graph via sums of squares of polynomials. Lect. Notes Comput. Sci. 3509, 136\u2013151 (2005)","journal-title":"Lect. Notes Comput. Sci."},{"key":"233_CR14","doi-asserted-by":"crossref","unstructured":"Gvozdenovi\u0107, N., Laurent, M.: Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization. SIAM J. Optim. (2008, to appear)","DOI":"10.1137\/070683520"},{"key":"233_CR15","doi-asserted-by":"crossref","unstructured":"Gvozdenovi\u0107, N., Laurent, M.: The operator \u03a8 for the chromatic number of a graph. SIAM J. Optim. (2008, to appear)","DOI":"10.1137\/050648237"},{"key":"233_CR16","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/S0196-6774(02)00217-1","volume":"45","author":"E. Halperin","year":"2002","unstructured":"Halperin E., Nathaniel R., Zwick U.: Coloring k-colorable graphs using relatively small palettes. J. Algorithms 45, 72\u201390 (2002)","journal-title":"J. Algorithms"},{"key":"233_CR17","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"Karger D., Motwani R., Sudan M.: Approximate graph coloring by semidefinite programming. J. Assoc. Comput. Machinery 45, 246\u2013265 (1998)","journal-title":"J. Assoc. Comput. Machinery"},{"key":"233_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/1193","volume":"1","author":"D.E. Knuth","year":"1994","unstructured":"Knuth D.E.: The sandwich theorem. Electron. J. Combinatorics 1, 1\u201348 (1994)","journal-title":"Electron. J. Combinatorics"},{"key":"233_CR19","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: On explicit exact SDP relaxation for nonlinear 0-1 programs. In: Ardal, K., Gerards, A.M.H. (eds.) Lecture Notes in Computer Science, vol. 2081, pp. 293\u2013303 (2001)","DOI":"10.1007\/3-540-45535-3_23"},{"key":"233_CR20","unstructured":"Laurent, M.: Strengthened semidefinite bounds for codes. Preprint, p. 17 (2005)"},{"key":"233_CR21","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/S0927-0507(05)12008-8","volume-title":"Handbook on Discrete Optimization","author":"M. Laurent","year":"2005","unstructured":"Laurent M., Rendl F.: Semidefinite programming and integer programming. In: Weismantel, R., Aardal, K., Nemhauser, G.(eds) Handbook on Discrete Optimization., pp. 393\u2013514. Elsevier B. V., Amsterdam (2005)"},{"key":"233_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"233_CR23","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz L., Schrijver A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1, 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"233_CR24","first-page":"45","volume":"30","author":"B.D. McKay","year":"1981","unstructured":"McKay B.D.: Practical graph isomorphism. Congressus Numerantium 30, 45\u201387 (1981)","journal-title":"Congressus Numerantium"},{"key":"233_CR25","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"K.G. Murty","year":"1987","unstructured":"Murty K.G., Kabadi S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39, 117\u2013129 (1987)","journal-title":"Math. Program."},{"key":"233_CR26","unstructured":"Parrilo, P.A.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. Ph.D. thesis, California Institute of Technology (2000)"},{"key":"233_CR27","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/05064401X","volume":"18","author":"J. Pe\u00f1a","year":"2007","unstructured":"Pe\u00f1a J., Vera J., Zuluaga L.F.: Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18, 87\u2013105 (2007)","journal-title":"SIAM J. Optim."},{"key":"233_CR28","unstructured":"Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Working paper (2006)"},{"key":"233_CR29","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1080\/10556789808805692","volume":"9","author":"A.J. Quist","year":"1998","unstructured":"Quist A.J., de Klerk E., Roos C., Terlaky T.: Copositive relaxation for general quadratic programming. Optim. Methods Softw. 9, 185\u2013209 (1998)","journal-title":"Optim. Methods Softw."},{"key":"233_CR30","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"25","author":"A. Schrijver","year":"1979","unstructured":"Schrijver A.: A comparison of the Delsarte and Lov\u00e1sz bounds. IEEE Trans. Inform. Theory IT 25, 425\u2013429 (1979)","journal-title":"IEEE Trans. Inform. Theory IT"},{"key":"233_CR31","volume-title":"Combinatorial Optimization\u2014Polyhedra and Efficiency, vol. B","author":"A. Schrijver","year":"2003","unstructured":"Schrijver A.: Combinatorial Optimization\u2014Polyhedra and Efficiency, vol. B. Springer, New York (2003)"},{"key":"233_CR32","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: A note on the theta number of Lov\u00e1sz and the generalized Delsarte bound. In: 35th Annual Symposium on Foundations of Computer Science, pp. 36\u201339 (1994)","DOI":"10.1109\/SFCS.1994.365707"},{"key":"233_CR33","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1017\/S0962492901000071","volume":"10","author":"M.J. Todd","year":"2001","unstructured":"Todd M.J.: Semidefinite optimization. Acta Numerica 10, 515\u2013560 (2001)","journal-title":"Acta Numerica"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-008-0233-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-008-0233-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-008-0233-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,11]],"date-time":"2021-09-11T14:30:56Z","timestamp":1631370656000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-008-0233-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,4]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["233"],"URL":"https:\/\/doi.org\/10.1007\/s10107-008-0233-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6,4]]}}}