{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T19:35:50Z","timestamp":1776886550128,"version":"3.51.2"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319774039","type":"print"},{"value":"9783319774046","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_47","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"640-652","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["New Integer Linear Programming Models for the Vertex Coloring Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1098-6358","authenticated-orcid":false,"given":"Adalat","family":"Jabrayilov","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7621-971X","authenticated-orcid":false,"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"47_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/978-3-540-68155-7_4","volume-title":"Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"T Achterberg","year":"2008","unstructured":"Achterberg, T., Berthold, T., Koch, T., Wolter, K.: Constraint integer programming: a new approach to integrate CP and MIP. In: Perron, L., Trick, M.A. (eds.) CPAIOR 2008. LNCS, vol. 5015, pp. 6\u201320. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-68155-7_4"},{"issue":"1","key":"47_CR2","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s10479-010-0716-z","volume":"179","author":"EK Burke","year":"2010","unstructured":"Burke, E.K., Mare\u010dek, J., Parkes, A.J., Rudov\u00e1, H.: A supernodal formulation of vertex colouring with applications in course timetabling. Ann. Oper. Res. 179(1), 105\u2013130 (2010)","journal-title":"Ann. Oper. Res."},{"issue":"7","key":"47_CR3","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/j.dam.2007.05.058","volume":"156","author":"MB Camp\u00ealo","year":"2008","unstructured":"Camp\u00ealo, M.B., Campos, V.A., Corr\u00eaa, R.C.: On the asymmetric representatives formulation for the vertex coloring problem. Discrete Appl. Math. 156(7), 1097\u20131111 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"47_CR4","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.ipl.2003.11.005","volume":"89","author":"MB Camp\u00ealo","year":"2004","unstructured":"Camp\u00ealo, M.B., Corr\u00eaa, R.C., Frota, Y.: Cliques, holes and the vertex coloring polytope. Inf. Process. Lett. 89(4), 159\u2013164 (2004)","journal-title":"Inf. Process. Lett."},{"key":"47_CR5","unstructured":"Campos, V., Corr\u00eaa, R.C., Delle Donne, D., Marenco, J., Wagler, A.: Polyhedral studies of vertex coloring problems: The asymmetric representatives formulation. ArXiv e-prints, August 2015"},{"issue":"Part 2","key":"47_CR6","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.dam.2016.09.018","volume":"217","author":"D Cornaz","year":"2017","unstructured":"Cornaz, D., Furini, F., Malaguti, E.: Solving vertex coloring problems as maximum weight stable set problems. Disc. Appl. Math. 217(Part 2), 151\u2013162 (2017)","journal-title":"Disc. Appl. Math."},{"key":"47_CR7","unstructured":"Benchmarking machines and testing solutions (2002). http:\/\/mat.gsia.cmu.edu\/COLOR02\/BENCHMARK\/benchmark.tar"},{"issue":"2","key":"47_CR8","doi-asserted-by":"publisher","first-page":"131","DOI":"10.7155\/jgaa.00064","volume":"7","author":"D Eppstein","year":"2003","unstructured":"Eppstein, D.: Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms Appl. 7(2), 131\u2013140 (2003)","journal-title":"J. Graph Algorithms Appl."},{"key":"47_CR9","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco, CA, USA (1979)"},{"key":"47_CR10","unstructured":"Gualandi, S. Chiarandini, M.: Graph coloring instances (2017). https:\/\/sites.google.com\/site\/graphcoloring\/vertex-coloring"},{"issue":"1","key":"47_CR11","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1287\/ijoc.1100.0436","volume":"24","author":"S Gualandi","year":"2012","unstructured":"Gualandi, S., Malucelli, F.: Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24(1), 81\u2013100 (2012)","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"47_CR12","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.disopt.2008.10.004","volume":"6","author":"P Hansen","year":"2009","unstructured":"Hansen, P., Labb\u00e9, M., Schindl, D.: Set covering and packing formulations of graph coloring: algorithms and first polyhedral results. Discrete Optim. 6(2), 135\u2013147 (2009)","journal-title":"Discrete Optim."},{"issue":"4","key":"47_CR13","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s12532-012-0042-3","volume":"4","author":"S Held","year":"2012","unstructured":"Held, S., Cook, W., Sewell, E.: Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Program. Comput. 4(4), 363\u2013381 (2012)","journal-title":"Math. Program. Comput."},{"key":"47_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-319-50106-2_17","volume-title":"Graph Drawing and Network Visualization","author":"A Jabrayilov","year":"2016","unstructured":"Jabrayilov, A., Mallach, S., Mutzel, P., R\u00fcegg, U., von Hanxleden, R.: Compact layered drawings of general directed graphs. In: Hu, Y., N\u00f6llenburg, M. (eds.) GD 2016. LNCS, vol. 9801, pp. 209\u2013221. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-50106-2_17"},{"key":"47_CR15","unstructured":"Jabrayilov, A., Mutzel, P. (2017). https:\/\/ls11-www.cs.tu-dortmund.de\/mutzel\/colorbenchmarks"},{"key":"47_CR16","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Trick, M. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26. AMS, Providence (1996)","DOI":"10.1090\/dimacs\/026"},{"issue":"2","key":"47_CR17","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.disopt.2010.07.005","volume":"8","author":"E Malaguti","year":"2011","unstructured":"Malaguti, E., Monaci, M., Toth, P.: An exact approach for the vertex coloring problem. Discrete Optim. 8(2), 174\u2013190 (2011)","journal-title":"Discrete Optim."},{"key":"47_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1475-3995.2009.00696.x","volume":"17","author":"E Malaguti","year":"2010","unstructured":"Malaguti, E., Toth, P.: A survey on vertex coloring problems. Int. Trans. Oper. Res. 17, 1\u201334 (2010)","journal-title":"Int. Trans. Oper. Res."},{"issue":"4","key":"47_CR19","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1287\/ijoc.8.4.344","volume":"8","author":"A Mehrotra","year":"1996","unstructured":"Mehrotra, A., Trick, M.: A column generation approach for graph coloring. INFORMS J. Comput. 8(4), 344\u2013354 (1996)","journal-title":"INFORMS J. Comput."},{"issue":"5","key":"47_CR20","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1016\/j.dam.2005.05.022","volume":"154","author":"I M\u00e9ndez-D\u00edaz","year":"2006","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P.: A branch-and-cut algorithm for graph coloring. Discrete Appl. Math. 154(5), 826\u2013847 (2006)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"47_CR21","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.dam.2006.07.010","volume":"156","author":"I M\u00e9ndez-D\u00edaz","year":"2008","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P.: A cutting plane algorithm for graph coloring. Discrete Appl. Math. 156(2), 159\u2013179 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"7","key":"47_CR22","doi-asserted-by":"publisher","first-page":"1724","DOI":"10.1016\/j.cor.2011.10.008","volume":"39","author":"PS Segundo","year":"2012","unstructured":"Segundo, P.S.: A new DSATUR-based algorithm for exact vertex coloring. Comput. Oper. Res. 39(7), 1724\u20131733 (2012)","journal-title":"Comput. Oper. Res."},{"key":"47_CR23","unstructured":"Sewell, E.: An improved algorithm for exact graph coloring. In: Johnson and Trick [16], pp. 359\u2013373"},{"key":"47_CR24","unstructured":"Trick, M.: DIMACS graph coloring instances (2002). http:\/\/mat.gsia.cmu.edu\/COLOR02\/"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:04:10Z","timestamp":1709827450000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}