{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T04:21:54Z","timestamp":1745986914673,"version":"3.40.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2013,2,6]],"date-time":"2013-02-06T00:00:00Z","timestamp":1360108800000},"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":[[2014,4]]},"DOI":"10.1007\/s10107-013-0636-1","type":"journal-article","created":{"date-parts":[[2013,2,5]],"date-time":"2013-02-05T03:54:01Z","timestamp":1360036441000},"page":"347-368","source":"Crossref","is-referenced-by-count":2,"title":["Chromatic Gallai identities operating on Lov\u00e1sz number"],"prefix":"10.1007","volume":"144","author":[{"given":"Denis","family":"Cornaz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philippe","family":"Meurdesoif","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,2,6]]},"reference":[{"key":"636_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"JA Bondy","year":"1976","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. American Elsevier Publishing Company, Inc, New York (1976)"},{"key":"636_CR2","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-Independence number gap recognition and related problems. Discret. Math. 306, 460\u2013463 (2006)","journal-title":"Discret. Math."},{"key":"636_CR3","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/j.dam.2007.05.058","volume":"156","author":"M Camp\u00ealo","year":"2008","unstructured":"Camp\u00ealo, M., Campos, V.A., Corr\u00eaa, R.C.: On the asymmetric representatives formulation for the vertex coloring problem. Discret. Appl. Math. 156, 1097\u20131111 (2008)","journal-title":"Discret. Appl. Math."},{"key":"636_CR4","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.ipl.2003.11.005","volume":"89","author":"M Camp\u00ealo","year":"2004","unstructured":"Camp\u00ealo, M., Corr\u00eaa, R., Frota, Y.: Cliques, holes and the vertex coloring polytope. Inf. Process. Lett. 89, 159\u2013164 (2004)","journal-title":"Inf. Process. Lett."},{"key":"636_CR5","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1016\/j.orl.2008.08.002","volume":"36","author":"D Cornaz","year":"2008","unstructured":"Cornaz, D., Jost, V.: A one-to-one correspondence between colorings and stable sets. Oper. Res. Lett. 36, 673\u2013676 (2008)","journal-title":"Oper. Res. Lett."},{"key":"636_CR6","doi-asserted-by":"crossref","unstructured":"Cornaz, D., Meurdesoif, P.: The sandwich line-graph. Electronic notes in discrete mathematics 36, 955\u2013960. (Proceedings of the conference ISCO 2010) (2010)","DOI":"10.1016\/j.endm.2010.05.121"},{"issue":"2\u20133","key":"636_CR7","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. 109(2\u20133), 345\u2013365 (2007)","journal-title":"Math. Program."},{"key":"636_CR8","volume-title":"Computers and intractability. A guide to the theory of NP-completness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completness. W. H. Freeman, San Francisco (1979)"},{"key":"636_CR9","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"636_CR10","unstructured":"Gvozdenovi\u0107, N.: Approximating the stability number and the chromatic number of a graph via semidefinite programming. PhD thesis, University of Amsterdam (2008)"},{"issue":"2","key":"636_CR11","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1137\/070683520","volume":"19","author":"N Gvozdenovi\u0107","year":"2008","unstructured":"Gvozdenovi\u0107, N., Laurent, M.: The operator $$\\Psi $$ for the chromatic number of a graph. SIAM J. Optim. 19(2), 592\u2013615 (2008)","journal-title":"SIAM J. Optim."},{"key":"636_CR12","doi-asserted-by":"crossref","first-page":"1155","DOI":"10.1016\/j.jctb.2012.06.001","volume":"102","author":"A Gy\u00e1rf\u00e1s","year":"2012","unstructured":"Gy\u00e1rf\u00e1s, A., Seb\u0151, A., Trotignon, N.: The chromatic gap and its extremes. J. Comb. Theory Ser. B 102, 1155\u20131178 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"636_CR13","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"636_CR14","doi-asserted-by":"crossref","unstructured":"Karger, D., Motwani, R., Sudan, M.: Approximate graph coloring by semidefinite programming. J. ACM 45(2), 246\u2013265 (1998)","DOI":"10.1145\/274787.274791"},{"issue":"1","key":"636_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/1193","volume":"1","author":"DE Knuth","year":"1994","unstructured":"Knuth, D.E.: The sandwich theorem. Electron. J. Comb. 1(1), 1\u201348 (1994)","journal-title":"Electron. J. Comb."},{"issue":"3","key":"636_CR16","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1002\/jgt.3190190313","volume":"19","author":"M Larsen","year":"1995","unstructured":"Larsen, M., Propp, J., Ullman, D.: The fractional chromatic number of Mycielski\u2019s graphs. J. Graph Theory 19(3), 411\u2013416 (1995)","journal-title":"J. Graph Theory"},{"key":"636_CR17","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. Inf.Theory 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf.Theory"},{"issue":"3","key":"636_CR18","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF02579227","volume":"2","author":"L Lov\u00e1sz","year":"1982","unstructured":"Lov\u00e1sz, L.: Tibor Gallai. Combinatorica 2(3), 203\u2013205 (1982)","journal-title":"Combinatorica"},{"issue":"2","key":"636_CR19","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\u20131 optimization. SIAM J. Optim. 1(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"636_CR20","unstructured":"McEliece, R.J., Rodemich, E.R., Rumsey Jr, H.C.: The Lov\u00e1sz bound and some generalizations. J. Comb. Inf. Syst. Sci. 3, 134\u2013152 (1978)"},{"issue":"3","key":"636_CR21","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/s101070100246","volume":"102","author":"P Meurdesoif","year":"2005","unstructured":"Meurdesoif, P.: Strengthening the Lov\u00e1sz Theta(G) bound for graph coloring. Math. Program. 102(3), 577\u2013588 (2005)","journal-title":"Math. Program."},{"key":"636_CR22","doi-asserted-by":"crossref","first-page":"161","DOI":"10.4064\/cm-3-2-161-162","volume":"3","author":"J Mycielski","year":"1955","unstructured":"Mycielski, J.: Sur le coloriage des graphes. Colloq. Math. 3, 161\u2013162 (1955)","journal-title":"Colloq. Math."},{"key":"636_CR23","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1080\/00207160701419114","volume":"85","author":"G Palubeckis","year":"2008","unstructured":"Palubeckis, G.: On the recursive largest first algorithm for graph coloring. Int. J. Comput. Math. 85, 191\u2013200 (2008)","journal-title":"Int. J. Comput. Math."},{"key":"636_CR24","doi-asserted-by":"crossref","first-page":"2075","DOI":"10.1016\/j.dam.2010.08.016","volume":"158","author":"G Palubeckis","year":"2010","unstructured":"Palubeckis, G.: Facet-inducing web and antiweb inequalities for the graph coloring polytope. Discret. Appl. Math. 158, 2075\u20132080 (2010)","journal-title":"Discret. Appl. Math."},{"key":"636_CR25","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"IT\u201325","author":"A Schrijver","year":"1979","unstructured":"Schrijver, A.: A comparison of the Delsarte and Lov\u00e1sz bounds. IEEE Trans. Inf. Theory IT\u201325, 425\u2013429 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"636_CR26","volume-title":"Combinatorial Optimization","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)"},{"key":"636_CR27","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: A note on the Theta number of Lov\u00e1sz and the generalized Delsarte bound, FOCS 1994 36\u201339.","DOI":"10.1109\/SFCS.1994.365707"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0636-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-013-0636-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0636-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T19:32:00Z","timestamp":1745955120000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-013-0636-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,6]]},"references-count":27,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["636"],"URL":"https:\/\/doi.org\/10.1007\/s10107-013-0636-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2013,2,6]]}}}