{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:08Z","timestamp":1740107108408,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T00:00:00Z","timestamp":1639612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T00:00:00Z","timestamp":1639612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["19K14583"],"award-info":[{"award-number":["19K14583"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s00373-021-02420-8","type":"journal-article","created":{"date-parts":[[2021,12,20]],"date-time":"2021-12-20T13:07:07Z","timestamp":1640005627000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Balanced Polychromatic 2-Coloring of Triangulations"],"prefix":"10.1007","volume":"38","author":[{"given":"Yoshihiro","family":"Asayama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2861-7152","authenticated-orcid":false,"given":"Naoki","family":"Matsumoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,12,16]]},"reference":[{"key":"2420_CR1","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s00454-009-9171-5","volume":"42","author":"N Alon","year":"2009","unstructured":"Alon, N., Berke, R., Buchin, K., Buchin, M., Csorba, P., Shannigrahi, S., Speckmann, B., Zumstein, P.: Polychromatic colorings of plane graphs. Discrete Comput. Geom. 42, 421\u2013442 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"2420_CR2","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/s00373-018-1909-5","volume":"34","author":"Y Asayama","year":"2018","unstructured":"Asayama, Y., Matsumoto, N., Nakamoto, A., Ogano, S.: Generating even triangulations on the Klein bottle. Graphs Combin. 34, 727\u2013757 (2018)","journal-title":"Graphs Combin."},{"key":"2420_CR3","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0012-365X(84)90074-8","volume":"52","author":"V Batagelj","year":"1984","unstructured":"Batagelj, V.: Inductive definition of two restricted classes of triangulations. Discrete Math. 52, 113\u2013121 (1984)","journal-title":"Discrete Math."},{"key":"2420_CR4","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory, Graduate Texts in Mathematics, vol. 244. Springer, New York (2008)","DOI":"10.1007\/978-1-84628-970-5"},{"key":"2420_CR5","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0925-7721(03)00027-0","volume":"26","author":"P Bose","year":"2003","unstructured":"Bose, P., Kirkpatrick, D., Li, Z.: Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces. Comput. Geom. Theory Appl. 26, 209\u2013219 (2003)","journal-title":"Comput. Geom. Theory Appl."},{"key":"2420_CR6","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/S0304-3975(03)00236-6","volume":"307","author":"J D\u00edaz","year":"2003","unstructured":"D\u00edaz, J., Do, N., Serna, M.J., Wormald, N.C.: Bounds on the max and min bisection of random cubic and random 4-regular graphs. Theor. Comput. Sci. 307, 531\u2013547 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"2420_CR7","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/j.tcs.2007.02.013","volume":"377","author":"J D\u00edaz","year":"2007","unstructured":"D\u00edaz, J., Kami\u0144ski, M.: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs. Theor. Comput. Sci. 377, 271\u2013276 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"2420_CR8","doi-asserted-by":"publisher","first-page":"2957","DOI":"10.1016\/j.disc.2008.07.035","volume":"309","author":"D Dimitrov","year":"2009","unstructured":"Dimitrov, D., Horev, E., Krakovski, R.: Polychromatic colorings of rectangular partitions. Discrete Math. 309, 2957\u20132960 (2009)","journal-title":"Discrete Math."},{"key":"2420_CR9","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.tcs.2018.06.027","volume":"818","author":"Q Feng","year":"2020","unstructured":"Feng, Q., Zhu, S., Wang, J.: An improved kernel for Max-Bisection above tight lower bound. Theor. Comput. Sci. 818, 12\u201321 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"2420_CR10","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0895480194265611","volume":"9","author":"F Hoffmann","year":"1996","unstructured":"Hoffmann, F., Kriegel, K.: A graph coloring result and its consequences for polygon guarding problems. SIAM J. Discrete Math. 9, 210\u2013224 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"2420_CR11","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1016\/j.ipl.2009.03.006","volume":"109","author":"E Horev","year":"2009","unstructured":"Horev, E., Katz, M.J., Krakovski, R., L\u00f6ffler, M.: Polychromatic 4-coloring of guillotine subdivisions. Inf. Process. Lett. 109, 690\u2013694 (2009)","journal-title":"Inf. Process. Lett."},{"key":"2420_CR12","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/j.disc.2011.11.016","volume":"312","author":"E Horev","year":"2012","unstructured":"Horev, E., Katz, M.J., Krakovski, R., Nakamoto, A.: Polychromatic 4-coloring of cubic bipartite plane graphs. Discrete Math. 312, 715\u2013719 (2012)","journal-title":"Discrete Math."},{"key":"2420_CR13","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1002\/jgt.20357","volume":"60","author":"E Horev","year":"2009","unstructured":"Horev, E., Krakovski, R.: Polychromatic colorings of bounded degree plane graphs. J. Graph Theory 60, 269\u2013283 (2009)","journal-title":"J. Graph Theory"},{"key":"2420_CR14","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1137\/S009753970139567X","volume":"35","author":"K Jansen","year":"2005","unstructured":"Jansen, K., Karpinski, M., Lingas, A., Seidel, E.: Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. SIAM J. Comput. 35, 110\u2013119 (2005)","journal-title":"SIAM J. Comput."},{"key":"2420_CR15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"2420_CR16","doi-asserted-by":"publisher","first-page":"2423","DOI":"10.1016\/j.disc.2013.07.005","volume":"313","author":"M Kobayashi","year":"2013","unstructured":"Kobayashi, M., Nakamoto, A., Yamaguchi, T.: Polychromatic 4-coloring of cubic even embeddings on the projective plane. Discrete Math. 313, 2423\u20132431 (2013)","journal-title":"Discrete Math."},{"key":"2420_CR17","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s12188-016-0172-z","volume":"87","author":"A K\u00fcndgen","year":"2017","unstructured":"K\u00fcndgen, A., Thomassen, C.: Spanning quadrangulations of triangulated surfaces. Abh. Math. Semin. Univ. Hambg. 87, 357\u2013368 (2017)","journal-title":"Abh. Math. Semin. Univ. Hambg."},{"key":"2420_CR18","doi-asserted-by":"publisher","first-page":"2035","DOI":"10.1016\/j.disc.2018.04.002","volume":"341","author":"N Matsumoto","year":"2018","unstructured":"Matsumoto, N., Nakamoto, A., Yamaguchi, T.: Generating even triangulations on the torus. Discrete Math. 341, 2035\u20132048 (2018)","journal-title":"Discrete Math."},{"key":"2420_CR19","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001)"},{"key":"2420_CR20","doi-asserted-by":"crossref","unstructured":"Mohar, B., \u0160krekovski, R.: The Gr\u00f6tzsch theorem for the hypergraph of maximal cliques. Electr. J. Combin., #R26 (1999)","DOI":"10.37236\/1458"},{"key":"2420_CR21","doi-asserted-by":"publisher","first-page":"2075","DOI":"10.1137\/140963340","volume":"29","author":"A Nakamoto","year":"2015","unstructured":"Nakamoto, A., Noguchi, K., Ozeki, K.: Extension to even triangulations. SIAM J. Discrete Math. 29, 2075\u20132087 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"2420_CR22","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1002\/jgt.22400","volume":"90","author":"A Nakamoto","year":"2019","unstructured":"Nakamoto, A., Noguchi, K., Ozeki, K.: Spanning bipartite quadrangulations of even triangulations. J. Graph Theory 90, 267\u2013287 (2019)","journal-title":"J. Graph Theory"},{"key":"2420_CR23","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J Petersen","year":"1891","unstructured":"Petersen, J.: Die Theorie der regul\u00e4ren graphs. Acta Math. 15, 193\u2013220 (1891)","journal-title":"Acta Math."},{"key":"2420_CR24","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1002\/jgt.20269","volume":"56","author":"Y Suzuki","year":"2007","unstructured":"Suzuki, Y., Watanabe, T.: Generating even triangulations of the projective plane. J. Graph Theory 56, 333\u2013349 (2007)","journal-title":"J. Graph Theory"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-021-02420-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-021-02420-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-021-02420-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T14:56:10Z","timestamp":1699973770000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-021-02420-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,16]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["2420"],"URL":"https:\/\/doi.org\/10.1007\/s00373-021-02420-8","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2021,12,16]]},"assertion":[{"value":"13 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 December 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"16"}}