{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:15:46Z","timestamp":1750220146447,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:00:00Z","timestamp":1654819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2022,6,10]]},"abstract":"<jats:p>e present a known theorem with the following authors. Part 1 was proven by Hopcroft and Tarjan [10]. Part 2 is easy. Part 3 was proven by Garey, Johnson, and Stockmeyer [6]. Part 4 was proven by Appel, Haken, and Koch [2, 3].<\/jats:p>","DOI":"10.1145\/3544979.3544987","type":"journal-article","created":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T07:52:51Z","timestamp":1658908371000},"page":"27-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Chromatic Number When Restricted to graphs with Bounded Genus or Bounded Crossing Number"],"prefix":"10.1145","volume":"53","author":[{"given":"William","family":"Gasarch","sequence":"first","affiliation":[{"name":"University of Maryland at College Park"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Hayes","sequence":"additional","affiliation":[{"name":"University of Maryland at College Park"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony","family":"Ostuni","sequence":"additional","affiliation":[{"name":"University of California, San Diego"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Davin","family":"Park","sequence":"additional","affiliation":[{"name":"University of Maryland at College Park"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Crossings, colorings, and cliques. Elec- tronic Journal of Combinatorics, 16(1)","author":"Albertson M. O.","year":"2009","unstructured":"M. O. Albertson , D. W. Cranston , and J. Fox . Crossings, colorings, and cliques. Elec- tronic Journal of Combinatorics, 16(1) , 2009 . http:\/\/math.mit.edu\/~fox\/paper-crossingcoloring.pdf. M. O. Albertson, D. W. Cranston, and J. Fox. Crossings, colorings, and cliques. Elec- tronic Journal of Combinatorics, 16(1), 2009. http:\/\/math.mit.edu\/~fox\/paper-crossingcoloring.pdf."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1256049011"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1256049012"},{"key":"e_1_2_1_4_1","volume-title":"Towards the Albertson conjecture. Electronic Journal Combina- torics, 17(1)","author":"J.","year":"2010","unstructured":"J. Bar--at and G. T--oth . Towards the Albertson conjecture. Electronic Journal Combina- torics, 17(1) , 2010 . https:\/\/arxiv.org\/abs\/0909.0413. J. Bar--at and G. T--oth. Towards the Albertson conjecture. Electronic Journal Combina- torics, 17(1), 2010. https:\/\/arxiv.org\/abs\/0909.0413."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/100784059"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0067363"},{"key":"e_1_2_1_8_1","first-page":"333","article-title":"On the number of crossings in a complete graph","volume":"2","author":"Harary F.","year":"1962","unstructured":"F. Harary and A. Hill . On the number of crossings in a complete graph . Proceedings of the Edinburgh Mathematical Society , 2 : 333 - 338 , 1962 --1963. F. Harary and A. Hill. On the number of crossings in a complete graph. Proceedings of the Edinburgh Mathematical Society, 2:333-338, 1962--1963.","journal-title":"Proceedings of the Edinburgh Mathematical Society"},{"key":"e_1_2_1_9_1","first-page":"332","volume-title":"Quarterly Journal of Mathematics","author":"Heawood P. J.","year":"1890","unstructured":"P. J. Heawood . Map-colour theorem . Quarterly Journal of Mathematics , pages 332 - 338 , 1890 . P. J. Heawood. Map-colour theorem. Quarterly Journal of Mathematics, pages 332-338, 1890."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(71)90019-6"},{"key":"e_1_2_1_11_1","first-page":"382","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing","author":"Kawarabayashi K.","year":"2007","unstructured":"K. Kawarabayashi and B. A. Reed . Computing crossing number in linear time. In D. S. Johnson and U. Feige, editors , Proceedings of the 39th Annual ACM Symposium on Theory of Computing , San Diego, California, USA, June 11--13 , 2007 , pages 382 - 390 . ACM, 2007. https:\/\/doi.org\/10.1145\/1250790.1250848. 10.1145\/1250790.1250848 K. Kawarabayashi and B. A. Reed. Computing crossing number in linear time. In D. S. Johnson and U. Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11--13, 2007, pages 382-390. ACM, 2007. https:\/\/doi.org\/10.1145\/1250790.1250848."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.05.002"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237986"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"e_1_2_1_15_1","volume-title":"On a conjecture by Anthony Hill","author":"Mohar B.","year":"2020","unstructured":"B. Mohar . On a conjecture by Anthony Hill , 2020 . https:\/\/arxiv.org\/pdf\/2009.03418.pdf. B. Mohar. On a conjecture by Anthony Hill, 2020. https:\/\/arxiv.org\/pdf\/2009.03418.pdf."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs and Surfaces","author":"Mohar B.","year":"2001","unstructured":"B. Mohar and C. Thomassen . Graphs and Surfaces . John Hopkins University Press , 2001 . B. Mohar and C. Thomassen. Graphs and Surfaces. John Hopkins University Press, 2001."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.07.040"},{"key":"e_1_2_1_18_1","volume-title":"The crossing number of K11 is 100. Journal of Graph theory, 100(56)","author":"Pan S.","year":"2007","unstructured":"S. Pan and R. B. Richter . The crossing number of K11 is 100. Journal of Graph theory, 100(56) , 2007 . S. Pan and R. B. Richter. The crossing number of K11 is 100. Journal of Graph theory, 100(56), 2007."},{"key":"e_1_2_1_19_1","volume-title":"Proc. of the National Academy of Science (USA), 60:438-445","author":"Ringel G.","year":"1967","unstructured":"G. Ringel and J. W. T. Young . Solution of the Heawood map colouring problem . Proc. of the National Academy of Science (USA), 60:438-445 , 1967 . G. Ringel and J. W. T. Young. Solution of the Heawood map colouring problem. Proc. of the National Academy of Science (USA), 60:438-445, 1967."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.52.3.688"},{"key":"e_1_2_1_21_1","volume-title":"Electronic Journal of Combinatorics","author":"Schaefer M.","year":"2009","unstructured":"M. Schaefer . The graph crossing number and its variants: a survey . Electronic Journal of Combinatorics , Dynamic Survey , 2009 . M. Schaefer. The graph crossing number and its variants: a survey. Electronic Journal of Combinatorics, Dynamic Survey, 2009."},{"key":"e_1_2_1_22_1","volume-title":"Crossing numbers of graphs","author":"Schaefer M.","year":"2017","unstructured":"M. Schaefer . Crossing numbers of graphs . CRC Press , 2017 . M. Schaefer. Crossing numbers of graphs. CRC Press, 2017."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.1722"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544979.3544987","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3544979.3544987","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:01Z","timestamp":1750186801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544979.3544987"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,10]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,10]]}},"alternative-id":["10.1145\/3544979.3544987"],"URL":"https:\/\/doi.org\/10.1145\/3544979.3544987","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2022,6,10]]},"assertion":[{"value":"2022-07-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}