{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T11:53:52Z","timestamp":1771329232227,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2006,9,19]],"date-time":"2006-09-19T00:00:00Z","timestamp":1158624000000},"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":[[2007,1,30]]},"DOI":"10.1007\/s10107-006-0026-z","type":"journal-article","created":{"date-parts":[[2006,9,18]],"date-time":"2006-09-18T08:58:24Z","timestamp":1158569904000},"page":"345-365","source":"Crossref","is-referenced-by-count":46,"title":["Semidefinite programming relaxations for graph coloring and maximal clique problems"],"prefix":"10.1007","volume":"109","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":[[2006,9,19]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Benson, S., Ye, Y.: Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation. In: Applications and Algorithms of Complementarity, pp. 1\u201318. Kluwer, Dordrecht (2000)","DOI":"10.1007\/978-1-4757-3279-5_1"},{"key":"26_CR2","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1137\/S1052623497328008","volume":"10","author":"S. Benson","year":"2000","unstructured":"Benson S., Ye Y., Zhang X. (2000): Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10, 443\u2013461","journal-title":"SIAM J. Optim."},{"key":"26_CR3","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1023\/A:1020209017701","volume":"24","author":"I.M. Bomze","year":"2002","unstructured":"Bomze I.M., de Klerk E. (2002): Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24, 163\u2013185","journal-title":"J. Global Optim."},{"key":"26_CR4","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"95","author":"S. Burer","year":"2003","unstructured":"Burer S., Monteiro R.D.C. (2003): A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95, 329\u2013357","journal-title":"Math. Program."},{"key":"26_CR5","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1137\/040609574","volume":"16","author":"S. Burer","year":"2006","unstructured":"Burer S., Vandenbussche D. (2006): Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16, 726\u2013750","journal-title":"SIAM J. Optim."},{"key":"26_CR6","unstructured":"Busygin, S., Pasechnik, D.V.: On $$\\bar\\chi(G)-\\alpha(G)>0$$ gap recognition and \u03b1(G)-upper bounds. Electronic Colloquium on Computational Complexity, Report No. 52\u00a0pp. 1\u20135 (2003)"},{"key":"26_CR7","unstructured":"Charikar, M.: On semidefinite programming relaxations for graph coloring and vertex cover. In: Proceedings of the 41th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 616\u2013620 (2002)"},{"key":"26_CR8","unstructured":"Dukanovic, I.: Semidefinite programming applied to graph coloring problem. PhD Thesis, University of Klagenfurt, Austria (2006) (forthcoming)"},{"key":"26_CR9","unstructured":"Dukanovic, I., Rendl, F.: A semidefinite programming based heuristic for graph coloring. Discrete Appl. Math. (to appear)"},{"key":"26_CR10","unstructured":"Dukanovic, I., Rendl, F.: Copositive programming motivated bounds on the clique and the chromatic number of a graph. Preprint (2006)"},{"key":"26_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. (2004): Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192, 95\u2013128","journal-title":"J. Pure Appl. Algebra"},{"key":"26_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel M., Lov\u00e1sz L., Schrijver A. (1988): Geometric Algorithms and Combinatorial Optimization. Springer, Berlin Heidelberg New York"},{"key":"26_CR13","doi-asserted-by":"crossref","first-page":"1014","DOI":"10.1137\/S1052623401394092","volume":"13","author":"G. Gruber","year":"2003","unstructured":"Gruber G., Rendl F. (2003): Computational experience with stable set relaxations. SIAM J. Optim. 13, 1014\u20131028","journal-title":"SIAM J. Optim."},{"key":"26_CR14","unstructured":"Gvozdenovi\u0107, N., Laurent, M.: Approximating the chromatic number of a graph by semidefinite programming. Working paper (2005)"},{"key":"26_CR15","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"C. Helmberg","year":"2000","unstructured":"Helmberg C., Rendl F. (2000): A spectral bundle method for semidefinite programming. SIAM J. Optim. 10, 673\u2013696","journal-title":"SIAM J. Optim."},{"key":"26_CR16","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF02239976","volume":"39","author":"A. Hertz","year":"1987","unstructured":"Hertz A., Werra D.D. (1987): Using tabu search for graph coloring. Computing 39, 345\u2013351","journal-title":"Computing"},{"key":"26_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. (1998): Approximate graph coloring by semidefinite programming. J. Assoc. Comput. Mach. 45, 246\u2013265","journal-title":"J. Assoc. Comput. Mach."},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"de Klerk, E., Pasechnik, D.V., Schrijver, A.: Reduction of symmetric semidefinite programs using the regular *-representation. Math. Program. (2005)(to appear)","DOI":"10.1007\/s10107-006-0039-7"},{"key":"26_CR19","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1023\/B:JOCO.0000038911.67280.3f","volume":"8","author":"E. Klerk de","year":"2004","unstructured":"de Klerk E., Pasechnik D.V., Warners J.P. (2004): On approximate graph colouring and max-k-cut algorithms based on the \u03b8-function. J. Combinat. Optim. 8, 267\u2013294","journal-title":"J. Combinat. Optim."},{"key":"26_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/1193","volume":"1","author":"D.E. Knuth","year":"1994","unstructured":"Knuth D.E. (1994): The sandwich theorem. Elect. J. Combinat. 1, 1\u201348","journal-title":"Elect. J. Combinat."},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Laurent, M., Rendl, F.: Semidefinite programming and integer programming. In: R.W.e. K. Aardal G. Nemhauser (ed.) Handbook on Discrete Optimization, pp. 393\u2013514. Elsevier, Amsterdam (2005)","DOI":"10.1016\/S0927-0507(05)12008-8"},{"key":"26_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. (1979): On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1\u20137","journal-title":"IEEE Trans. Inf. Theory"},{"key":"26_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. (1991): Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1, 166\u2013190","journal-title":"SIAM J. Optim."},{"key":"26_CR24","unstructured":"Malick, J., Povh, J., Rendl, F., Wiegele, A.: A boundary point method to solve semidefinite programs. Working paper (2006)"},{"key":"26_CR25","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1007\/3-540-45535-3_24","volume":"2081","author":"F. Margot","year":"2001","unstructured":"Margot F. (2001): Pruning by isomorphism in branch-and-cut. Lect. Notes Comput. Sci. 2081, 304\u2013317","journal-title":"Lect. Notes Comput. Sci."},{"key":"26_CR26","first-page":"134","volume":"3","author":"J.R. McEliece","year":"1978","unstructured":"McEliece J.R., Rodemich E., Rumsey H. (1978): The Lov\u00e1sz bound and some generalizations. J. Combinat. Syst. Sci. 3, 134\u2013152","journal-title":"J. Combinat. Syst. Sci."},{"key":"26_CR27","first-page":"45","volume":"30","author":"B.D. McKay","year":"1981","unstructured":"McKay B.D. (1981): Practical graph isomorphism. Congressus Numer. 30, 45\u201387","journal-title":"Congressus Numer."},{"key":"26_CR28","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/s101070100246","volume":"102","author":"P. Meurdesoif","year":"2005","unstructured":"Meurdesoif P. (2005): Strengthening the Lov\u00e1sz $$\\theta(\\overline{G})$$ bound for graph coloring. Math. Program. 102, 577\u2013588","journal-title":"Math. Program."},{"key":"26_CR29","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. (1987): Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39, 117\u2013129","journal-title":"Math. Program."},{"key":"26_CR30","unstructured":"Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD Thesis, California Institute of Technology (2000)"},{"key":"26_CR31","doi-asserted-by":"crossref","unstructured":"Parrilo, P.A., Sturmfels, B.: Minimizing polynomial functions. In: S. Basu, L.G.V. (eds.) Algorithmic and quantitative real algebraic geometry. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 60, pp. 83\u201399. AMS New york (2003)","DOI":"10.1090\/dimacs\/060\/08"},{"key":"26_CR32","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"25","author":"A. Schrijver","year":"1979","unstructured":"Schrijver A. (1979): A comparison of the Delsarte and Lov\u00e1sz bounds. IEEE Trans. Info. Theory IT-25, 425\u2013429","journal-title":"IEEE Trans. Info. Theory IT-"},{"key":"26_CR33","doi-asserted-by":"crossref","first-page":"2859","DOI":"10.1109\/TIT.2005.851748","volume":"51","author":"A. Schrijver","year":"2004","unstructured":"Schrijver A. (2004): New code upper bounds from the Terwilliger algebra. IEEE Trans. Infor. Theory 51, 2859\u20132866","journal-title":"IEEE Trans. Infor. Theory"},{"key":"26_CR34","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":"26_CR35","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1137\/S1052623400376378","volume":"12","author":"K. Toh","year":"2002","unstructured":"Toh K., Kojima M. (2002): Solving some large scale semidefinite programs via the conjugate residual method. SIAM J. Optim. 12, 669\u2013691","journal-title":"SIAM J. Optim."},{"issue":"(5","key":"26_CR36","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0020-0190(01)00229-0","volume":"81","author":"A. Vesel","year":"2002","unstructured":"Vesel A., \u017derovnik J. (2002): Improved lower bound on the Shannon capacity of C7. Inf. Process. Lett. 81 (5): 277\u2013282","journal-title":"Inf. Process. Lett."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0026-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-006-0026-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0026-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T21:42:17Z","timestamp":1683582137000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-006-0026-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9,19]]},"references-count":36,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2007,1,30]]}},"alternative-id":["26"],"URL":"https:\/\/doi.org\/10.1007\/s10107-006-0026-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9,19]]}}}