{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:12:42Z","timestamp":1764173562759},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s00454-009-9171-5","type":"journal-article","created":{"date-parts":[[2009,6,29]],"date-time":"2009-06-29T18:25:00Z","timestamp":1246299900000},"page":"421-442","source":"Crossref","is-referenced-by-count":20,"title":["Polychromatic Colorings of Plane Graphs"],"prefix":"10.1007","volume":"42","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Berke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Buchin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maike","family":"Buchin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P\u00e9ter","family":"Csorba","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saswata","family":"Shannigrahi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bettina","family":"Speckmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Zumstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,6,30]]},"reference":[{"key":"9171_CR1","doi-asserted-by":"crossref","first-page":"4460","DOI":"10.1016\/j.disc.2007.08.090","volume":"308","author":"N. Alon","year":"2008","unstructured":"Alon, N.: Problems and results in extremal combinatorics, ii. Discrete Math. 308, 4460\u20134472 (2008)","journal-title":"Discrete Math."},{"key":"9171_CR2","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1137\/060649422","volume":"21","author":"N. Alon","year":"2007","unstructured":"Alon, N., Krech, A., Szab\u00f3, T.: Tur\u00e1n\u2019s theorem in the hypercube. SIAM J. Discrete Math. 21, 66\u201372 (2007)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"9171_CR3","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0925-7721(95)00034-8","volume":"7","author":"P. Bose","year":"1997","unstructured":"Bose, P., Shermer, T., Toussaint, G., Zhu, B.: Guarding polyhedral terrains. Comput. Geom.: Theory Appl. 7(3), 173\u2013185 (1997)","journal-title":"Comput. Geom.: Theory Appl."},{"issue":"3","key":"9171_CR4","doi-asserted-by":"crossref","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(3), 209\u2013219 (2003)","journal-title":"Comput. Geom.: Theory Appl."},{"issue":"6","key":"9171_CR5","doi-asserted-by":"crossref","first-page":"2957","DOI":"10.1016\/j.disc.2008.07.035","volume":"30","author":"D. Dimitrov","year":"2009","unstructured":"Dimitrov, D., Horev, E., Krakovski, R.: A note on polychromatic coloring of rectangular partitions. Discrete Math. 30(6), 2957\u20132960 (2009)","journal-title":"Discrete Math."},{"key":"9171_CR6","unstructured":"Dinitz, Y., Katz, M.J., Krakovski, R.: Guarding rectangular partitions. In: Abstracts 23rd European Workshop on Computational Geometry, pp. 30\u201333 (2007)"},{"key":"9171_CR7","doi-asserted-by":"crossref","unstructured":"Horev, E., Katz, M.J., Krakovski, R.: Polychromatic coloring of cubic bipartite plane graphs (2009, submitted)","DOI":"10.1002\/jgt.20357"},{"key":"9171_CR8","unstructured":"Guenin, B.: Packing T-joins and edge colouring in planar graphs. Manuscript (2003)"},{"key":"9171_CR9","series-title":"Lecture Notes in Math.","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/BFb0070378","volume-title":"Theory and Applications of Graphs","author":"R.P. Gupta","year":"1978","unstructured":"Gupta, R.P.: On the chromatic index and the cover index of a multigraph. In: Theory and Applications of Graphs, Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976. Lecture Notes in Math., vol. 642, pp. 204\u2013215. Springer, Berlin (1978)"},{"key":"9171_CR10","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/jgt.3190100202","volume":"10","author":"S. Louis Hakimi","year":"1986","unstructured":"Louis Hakimi, S., Kariv, O.: Generalization of edge-coloring in graphs. J. Graph Theory 10, 139\u2013154 (1986)","journal-title":"J. Graph Theory"},{"key":"9171_CR11","first-page":"270","volume":"29","author":"P.J. Heawood","year":"1898","unstructured":"Heawood, P.J.: On the four-color map theorem. Quart. J. Pure Appl. Math. 29, 270\u2013285 (1898)","journal-title":"Quart. J. Pure Appl. Math."},{"key":"9171_CR12","doi-asserted-by":"crossref","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":"9171_CR13","unstructured":"Horev, E., Krakovski, R.: Face-respecting colorings of bounded degree plane graphs. Manuscript (2007)"},{"issue":"3","key":"9171_CR14","doi-asserted-by":"crossref","first-page":"193","DOI":"10.2307\/2369235","volume":"2","author":"A.B. Kempe","year":"1879","unstructured":"Kempe, A.B.: On the geographical problem of four colors. Am. J. Math. 2(3), 193\u2013200 (1879)","journal-title":"Am. J. Math."},{"key":"9171_CR15","doi-asserted-by":"crossref","unstructured":"Keszegh, B.: Polychromatic colorings of n-dimensional guillotine-partitions In: COCOON, pp. 110\u2013118 (2008)","DOI":"10.1007\/978-3-540-69733-6_12"},{"key":"9171_CR16","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. North-Holland, Amsterdam (1986)"},{"key":"9171_CR17","doi-asserted-by":"crossref","first-page":"R26","DOI":"10.37236\/1458","volume":"6","author":"B. Mohar","year":"1999","unstructured":"Mohar, B., Skrekovski, R.: The Gr\u00f6tzsch theorem for the hypergraph of maximal cliques. Electron. J. Comb. 6, R26 (1999)","journal-title":"Electron. J. Comb."},{"issue":"2","key":"9171_CR18","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/49097.49099","volume":"19","author":"B.M.E. Moret","year":"1988","unstructured":"Moret, B.M.E.: Planar NAE3SAT is in P. SIGACT News 19(2), 51\u201354 (1988)","journal-title":"SIGACT News"},{"issue":"2","key":"9171_CR19","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1137\/07068014X","volume":"22","author":"D. Offner","year":"2008","unstructured":"Offner, D.: Polychromatic colorings of subcubes of the hypercube. SIAM J. Discrete Math. 22(2), 450\u2013454 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"9171_CR20","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1112\/plms\/s3-38.3.423","volume":"3","author":"P.D. Seymour","year":"1979","unstructured":"Seymour, P.D.: On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. Lond. Math. Soc. 3, 423\u2013460 (1979)","journal-title":"Proc. Lond. Math. Soc."},{"key":"9171_CR21","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0167-5060(08)70391-1","volume":"55","author":"R. Steinberg","year":"1993","unstructured":"Steinberg, R.: The state of the three color problem. Ann. Discrete Math. 55, 211\u2013248 (1993)","journal-title":"Ann. Discrete Math."},{"issue":"3","key":"9171_CR22","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1008293.1008294","volume":"5","author":"L. Stockmeyer","year":"1973","unstructured":"Stockmeyer, L.: Planar 3-colorability is polynomial complete. SIGACT News 5(3), 19\u201325 (1973)","journal-title":"SIGACT News"},{"key":"9171_CR23","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"1996","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall, New York (1996)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9171-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T03:21:12Z","timestamp":1589944872000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9171-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,30]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9171"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9171-5","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6,30]]}}}