{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:17:47Z","timestamp":1757621867719,"version":"3.44.0"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783032002808"},{"type":"electronic","value":"9783032002815"}],"license":[{"start":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T00:00:00Z","timestamp":1754870400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T00:00:00Z","timestamp":1754870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-00281-5_24","type":"book-chapter","created":{"date-parts":[[2025,8,10]],"date-time":"2025-08-10T11:38:35Z","timestamp":1754825915000},"page":"398-414","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["New Formulation for\u00a0Coloring Circle Graphs"],"prefix":"10.1007","author":[{"given":"Masato","family":"Tanaka","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0106-0980","authenticated-orcid":false,"given":"Tomomi","family":"Matsui","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,11]]},"reference":[{"issue":"1\u20133","key":"24_CR1","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0012-365X(95)00349-2","volume":"152","author":"AA Ageev","year":"1996","unstructured":"Ageev, A.A.: A triangle-free circle graph with chromatic number 5. Discret. Math. 152(1\u20133), 295\u2013298 (1996)","journal-title":"Discret. Math."},{"issue":"1","key":"24_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(92)90200-T","volume":"36","author":"A Apostolico","year":"1992","unstructured":"Apostolico, A., Atallah, M.J., Hambrusch, S.E.: New clique and independent set algorithms for circle graphs. Discret. Appl. Math. 36(1), 1\u201324 (1992)","journal-title":"Discret. Appl. Math."},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Aslan, M., Baykan, N.A.: A performance comparison of graph coloring algorithms. Int. J. Intell. Syst. Appl. Eng. 4(Special Issue-1), 1\u20137 (2016)","DOI":"10.18201\/ijisae.273053"},{"issue":"1\u20133","key":"24_CR4","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0166-218X(99)00245-0","volume":"103","author":"M Avriel","year":"2000","unstructured":"Avriel, M., Penn, M., Shpirer, N.: Container ship stowage problem: complexity and connection to the coloring of circle graphs. Discret. Appl. Math. 103(1\u20133), 271\u2013279 (2000)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"24_CR5","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/PL00020912","volume":"49","author":"U Blasum","year":"1999","unstructured":"Blasum, U., Bussieck, M.R., Hochst\u00e4ttler, W., Moll, C., Scheel, H.H., Winter, T.: Scheduling trams in the morning. Math. Methods Oper. Res. 49(1), 137\u2013148 (1999)","journal-title":"Math. Methods Oper. Res."},{"issue":"7","key":"24_CR6","doi-asserted-by":"publisher","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(7), 1097\u20131111 (2008)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"24_CR7","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(02)00418-3","volume":"131","author":"E \u010cenek","year":"2003","unstructured":"\u010cenek, E., Stewart, L.: Maximum independent set and maximum clique algorithms for overlap graphs. Discret. Appl. Math. 131(1), 77\u201391 (2003)","journal-title":"Discret. Appl. Math."},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/j.endm.2007.07.072","volume":"29","author":"J \u010cern\u1ef3","year":"2007","unstructured":"\u010cern\u1ef3, J.: Coloring circle graphs. Electron. Notes Discret. Math. 29, 457\u2013461 (2007)","journal-title":"Electron. Notes Discret. Math."},{"issue":"2","key":"24_CR9","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.jda.2006.05.001","volume":"5","author":"S Cornelsen","year":"2007","unstructured":"Cornelsen, S., Di Stefano, G.: Track assignment. J. Discret. Algorithm 5(2), 250\u2013261 (2007)","journal-title":"J. Discret. Algorithm"},{"issue":"12","key":"24_CR10","first-page":"5121","volume":"150","author":"J Davies","year":"2022","unstructured":"Davies, J.: Improved bounds for colouring circle graphs. Proc. Am. Math. Soc. 150(12), 5121\u20135135 (2022)","journal-title":"Proc. Am. Math. Soc."},{"issue":"3","key":"24_CR11","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1112\/blms.12447","volume":"53","author":"J Davies","year":"2021","unstructured":"Davies, J., McCarty, R.: Circle graphs are quadratically $$\\chi -$$bounded. Bull. Lond. Math. Soc. 53(3), 673\u2013679 (2021)","journal-title":"Bull. Lond. Math. Soc."},{"issue":"7\u20138","key":"24_CR12","doi-asserted-by":"publisher","first-page":"1072","DOI":"10.1016\/j.dam.2012.01.002","volume":"160","author":"M Demange","year":"2012","unstructured":"Demange, M., Di Stefano, G., Leroy-Beaulieu, B.: On the online track assignment problem. Discret. Appl. Math. 160(7\u20138), 1072\u20131093 (2012)","journal-title":"Discret. Appl. Math."},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"RP Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51, 161\u2013166 (1950)","journal-title":"Ann. Math."},{"issue":"2","key":"24_CR14","first-page":"339","volume":"6","author":"V Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107, V., Wood, D.R.: On linear layouts of graphs. Discret. Math. Theor. Comput. Sci. 6(2), 339\u2013358 (2004)","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/j.dam.2012.12.021","volume":"164","author":"G Dur\u00e1n","year":"2014","unstructured":"Dur\u00e1n, G., Grippo, L.N., Safe, M.D.: Structural results on circular-arc graphs and circle graphs: a survey and the main open problems. Discret. Appl. Math. 164, 427\u2013443 (2014)","journal-title":"Discret. Appl. Math."},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"Even, S., Itai, A.: Queues, stacks and graphs. In: Theory of Machines and Computations, pp. 71\u201386. Elsevier (1971)","DOI":"10.1016\/B978-0-12-417750-5.50011-7"},{"issue":"1","key":"24_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0166-218X(96)00013-3","volume":"74","author":"S Felsner","year":"1997","unstructured":"Felsner, S., M\u00fcller, R., Wernisch, L.: Trapezoid graphs and generalizations, geometry and algorithms. Discret. Appl. Math. 74(1), 13\u201332 (1997)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"24_CR18","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D Fulkerson","year":"1965","unstructured":"Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"issue":"3","key":"24_CR19","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1287\/trsc.35.3.322.10151","volume":"35","author":"G Gallo","year":"2001","unstructured":"Gallo, G., Miele, F.D.: Dispatching buses in parking depots. Transp. Sci. 35(3), 322\u2013330 (2001)","journal-title":"Transp. Sci."},{"issue":"2","key":"24_CR20","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"MR Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The complexity of coloring circular arcs and chords. SIAM J. Algebraic Discret. Methods 1(2), 216\u2013227 (1980)","journal-title":"SIAM J. Algebraic Discret. Methods"},{"issue":"3","key":"24_CR21","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1002\/net.3230030305","volume":"3","author":"F Gavril","year":"1973","unstructured":"Gavril, F.: Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3(3), 261\u2013273 (1973)","journal-title":"Networks"},{"key":"24_CR22","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Elsevier (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"issue":"2","key":"24_CR23","doi-asserted-by":"publisher","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(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"24_CR24","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer (1987)","DOI":"10.1007\/978-3-642-97881-4"},{"issue":"1","key":"24_CR25","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/BF01580250","volume":"6","author":"AJ Hoffman","year":"1974","unstructured":"Hoffman, A.J.: A generalization of max flow-min cut. Math. Program. Ser. A and B 6(1), 352\u2013359 (1974)","journal-title":"Math. Program. Ser. A and B"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Hoffman, A.J., Kruskal, J.B.: Integral boundary points of convex polyhedra. In: Linear Inequalities and Related Systems, pp. 223\u2013246. Princeton University Press (1956)","DOI":"10.1515\/9781400881987-014"},{"key":"24_CR27","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Springer (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"14","key":"24_CR28","doi-asserted-by":"publisher","first-page":"1983","DOI":"10.1016\/j.dam.2006.03.003","volume":"154","author":"JM Keil","year":"2006","unstructured":"Keil, J.M., Stewart, L.: Approximating the minimum clique cover and other hard problems in subtree filament graphs. Discret. Appl. Math. 154(14), 1983\u20131995 (2006)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"24_CR29","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"LG Khachiyan","year":"1980","unstructured":"Khachiyan, L.G.: Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20(1), 53\u201372 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"24_CR30","doi-asserted-by":"publisher","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\u201348 (1994)","journal-title":"Electron. J. Comb."},{"key":"24_CR31","doi-asserted-by":"crossref","unstructured":"K\u00f6nig, F.G., L\u00fcbbecke, M.E.: Sorting with complete networks of stacks. In: International Symposium on Algorithms and Computation, pp. 895\u2013906. Springer (2008)","DOI":"10.1007\/978-3-540-92182-0_78"},{"key":"24_CR32","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1090\/conm\/342\/06137","volume":"342","author":"A Kostochka","year":"2004","unstructured":"Kostochka, A.: Coloring intersection graphs of geometric figures with a given clique number. Contemp. Math. 342, 127\u2013138 (2004)","journal-title":"Contemp. Math."},{"issue":"1","key":"24_CR33","doi-asserted-by":"publisher","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), 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"24_CR34","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1002\/net.3230110305","volume":"11","author":"D Rotem","year":"1981","unstructured":"Rotem, D., Urrutia, J.: Finding maximum cliques in circle graphs. Networks 11(3), 269\u2013278 (1981)","journal-title":"Networks"},{"issue":"5","key":"24_CR35","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(85)90093-6","volume":"21","author":"KJ Supowit","year":"1985","unstructured":"Supowit, K.J.: Decomposing a set of points into chains, with applications to permutation and circle graphs. Inf. Process. Lett. 21(5), 249\u2013252 (1985)","journal-title":"Inf. Process. Lett."},{"key":"24_CR36","doi-asserted-by":"crossref","unstructured":"Valiente, G.: A new simple algorithm for the maximum-weight independent set problem on circle graphs. In: International Symposium on Algorithms and Computation, pp. 129\u2013137. Springer (2003)","DOI":"10.1007\/978-3-540-24587-2_15"},{"key":"24_CR37","doi-asserted-by":"crossref","unstructured":"Wang, N., Zhang, Z., Lim, A.: The stowage stack minimization problem with zero rehandle constraint. In: International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, pp. 456\u2013465. Springer (2014)","DOI":"10.1007\/978-3-319-07467-2_48"}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry, Graphs, and Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-00281-5_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T16:04:05Z","timestamp":1757347445000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-00281-5_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,11]]},"ISBN":["9783032002808","9783032002815"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-00281-5_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,8,11]]},"assertion":[{"value":"11 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"JCDCGGG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japanese Conference on Discrete and Computational Geometry, Graphs, and Games","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"jcdcg2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.alg.cei.uec.ac.jp\/itohiro\/JCDCGG\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}