{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:34:11Z","timestamp":1753886051751,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520005","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"234-247","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Brooks\u2019 theorem in graph streams: a single-pass semi-streaming algorithm for \u2206-coloring"],"prefix":"10.1145","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"Rutgers University, USA"}]},{"given":"Pankaj","family":"Kumar","sequence":"additional","affiliation":[{"name":"Charles University in Prague, Czechia"}]},{"given":"Parth","family":"Mittal","sequence":"additional","affiliation":[{"name":"Rutgers University, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Higher Lower Bounds. CoRR, abs\/1901.01630","author":"Abboud Amir","year":"2019","unstructured":"Amir Abboud , Keren Censor-Hillel , Seri Khoury , and Ami Paz . 2019. Smaller Cuts , Higher Lower Bounds. CoRR, abs\/1901.01630 ( 2019 ). Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. 2019. Smaller Cuts, Higher Lower Bounds. CoRR, abs\/1901.01630 (2019)."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_3_2_1_3_1","volume-title":"APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference, Jaroslaw Byrka and Raghu Meka (Eds.) (LIPIcs","volume":"22","author":"Alon Noga","year":"2020","unstructured":"Noga Alon and Sepehr Assadi . 2020 . Palette Sparsification Beyond (\u0394 + 1) Vertex Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference, Jaroslaw Byrka and Raghu Meka (Eds.) (LIPIcs , Vol. 176). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 6:1\u20136: 22 . Noga Alon and Sepehr Assadi. 2020. Palette Sparsification Beyond (\u0394 + 1) Vertex Coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference, Jaroslaw Byrka and Raghu Meka (Eds.) (LIPIcs, Vol. 176). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 6:1\u20136:22."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01204715"},{"key":"e_1_3_2_1_5_1","volume-title":"Deterministic Graph Coloring in the Streaming Model. CoRR, abs\/2109.14891. To appear in STOC 2022","author":"Assadi Sepehr","year":"2021","unstructured":"Sepehr Assadi , Andrew Chen , and Glenn Sun . 2021.. Deterministic Graph Coloring in the Streaming Model. CoRR, abs\/2109.14891. To appear in STOC 2022 ( 2021 .), arXiv:2109.14891.. arxiv:2109.14891 Sepehr Assadi, Andrew Chen, and Glenn Sun. 2021.. Deterministic Graph Coloring in the Streaming Model. CoRR, abs\/2109.14891. To appear in STOC 2022 (2021.), arXiv:2109.14891.. arxiv:2109.14891"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.48"},{"key":"e_1_3_2_1_7_1","volume-title":"Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. CoRR, abs\/2109.14528. To appear in ITCS","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi and Chen Wang . 2021. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. CoRR, abs\/2109.14528. To appear in ITCS 2022 . (2021), arXiv:2109.14528. arxiv:2109.14528 Sepehr Assadi and Chen Wang. 2021. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. CoRR, abs\/2109.14528. To appear in ITCS 2022. (2021), arXiv:2109.14528. arxiv:2109.14528"},{"key":"e_1_3_2_1_8_1","unstructured":"Bradley Baetz and David R Wood. 2014. Brooks\u2019 vertex-colouring theorem in linear time. arXiv preprint arXiv:1401.8023. Bradley Baetz and David R Wood. 2014. Brooks\u2019 vertex-colouring theorem in linear time. arXiv preprint arXiv:1401.8023."},{"key":"e_1_3_2_1_9_1","volume-title":"Distributed \u0394 -Coloring Plays Hide-and-Seek. CoRR, abs\/2110.00643. To appear in STOC","author":"Balliu Alkida","year":"2022","unstructured":"Alkida Balliu , Sebastian Brandt , Fabian Kuhn , and Dennis Olivetti . 2021. Distributed \u0394 -Coloring Plays Hide-and-Seek. CoRR, abs\/2110.00643. To appear in STOC 2022 . (2021). Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. 2021. Distributed \u0394 -Coloring Plays Hide-and-Seek. CoRR, abs\/2110.00643. To appear in STOC 2022. (2021)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_3_2_1_11_1","volume-title":"Streaming and Massively Parallel Algorithms for Edge Coloring. In 27th Annual European Symposium on Algorithms, ESA 2019","volume":"14","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad , Mahsa Derakhshan , MohammadTaghi Hajiaghayi , Marina Knittel , and Hamed Saleh . 2019 . Streaming and Massively Parallel Algorithms for Edge Coloring. In 27th Annual European Symposium on Algorithms, ESA 2019 , September 9-11, 2019, Munich\/Garching, Germany, Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.) (LIPIcs , Vol. 144). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315: 14 . Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. 2019. Streaming and Massively Parallel Algorithms for Edge Coloring. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich\/Garching, Germany, Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.) (LIPIcs, Vol. 144). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315:14."},{"key":"e_1_3_2_1_12_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 11:1\u201311:21","author":"Bera Suman K.","year":"2020","unstructured":"Suman K. Bera , Amit Chakrabarti , and Prantar Ghosh . 2020 . Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 11:1\u201311:21 . Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. 2020. Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 11:1\u201311:21."},{"key":"e_1_3_2_1_13_1","volume-title":"Coloring in Graph Streams. CoRR, abs\/1807.07640","author":"Bera Suman Kalyan","year":"2018","unstructured":"Suman Kalyan Bera and Prantar Ghosh . 2018. Coloring in Graph Streams. CoRR, abs\/1807.07640 ( 2018 ). Suman Kalyan Bera and Prantar Ghosh. 2018. Coloring in Graph Streams. CoRR, abs\/1807.07640 (2018)."},{"key":"e_1_3_2_1_14_1","volume-title":"12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, James R. Lee (Ed.) (LIPIcs","volume":"19","author":"Bhattacharya Anup","year":"2021","unstructured":"Anup Bhattacharya , Arijit Bishnu , Gopinath Mishra , and Anannya Upasana . 2021 . Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming! . In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, James R. Lee (Ed.) (LIPIcs , Vol. 185). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315: 19 . Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, and Anannya Upasana. 2021. Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, James R. Lee (Ed.) (LIPIcs, Vol. 185). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315:19."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(77)90037-5"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897570"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002168X"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_3_2_1_19_1","volume-title":"Adversarially Robust Coloring for Graph Streams. CoRR, abs\/2109.11130. To appear in ITCS 2022","author":"Chakrabarti Amit","year":"2021","unstructured":"Amit Chakrabarti , Prantar Ghosh , and Manuel Stoeckl . 2021. Adversarially Robust Coloring for Graph Streams. CoRR, abs\/2109.11130. To appear in ITCS 2022 ( 2021 ). Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. 2021. Adversarially Robust Coloring for Graph Streams. CoRR, abs\/2109.11130. To appear in ITCS 2022 (2021)."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188964"},{"key":"e_1_3_2_1_21_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","volume":"14","author":"Cormode Graham","year":"2019","unstructured":"Graham Cormode , Jacques Dark , and Christian Konrad . 2019 . Independent Sets in Vertex-Arrival Streams. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 , July 9-12, 2019, Patras, Greece, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.) (LIPIcs , Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 45:1\u201345: 14 . Graham Cormode, Jacques Dark, and Christian Konrad. 2019. Independent Sets in Vertex-Arrival Streams. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.) (LIPIcs, Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 45:1\u201345:14."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21847"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405751"},{"key":"e_1_3_2_1_24_1","volume-title":"ACM Symposium on Principles of Distributed Computing","author":"Czumaj Artur","year":"2021","unstructured":"Artur Czumaj , Peter Davies , and Merav Parter . 2021 . Improved Deterministic (\u0394 + 1) Coloring in Low-Space MPC. In PODC \u201921 : ACM Symposium on Principles of Distributed Computing , Virtual Event, Italy , July 26-30, 2021, Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen (Eds.). ACM, 469\u2013479. Artur Czumaj, Peter Davies, and Merav Parter. 2021. Improved Deterministic (\u0394 + 1) Coloring in Low-Space MPC. In PODC \u201921: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen (Eds.). ACM, 469\u2013479."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2013.6638794"},{"key":"e_1_3_2_1_26_1","volume-title":"Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium. 26","author":"Erdos Paul","year":"1979","unstructured":"Paul Erdos , Arthur L Rubin , and Herbert Taylor . 1979 . Choosability in graphs . In Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium. 26 , 125\u2013157. Paul Erdos, Arthur L Rubin, and Herbert Taylor. 1979. Choosability in graphs. In Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium. 26, 125\u2013157."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212764"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403008"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0051-5"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451089"},{"key":"e_1_3_2_1_33_1","volume-title":"Near-Optimal Distributed Degree+1 Coloring. CoRR, abs\/2112.00604. To appear in STOC","author":"Halld\u00f3rsson Magn\u00fas M.","year":"2022","unstructured":"Magn\u00fas M. Halld\u00f3rsson , Fabian Kuhn , Alexandre Nolin , and Tigran Tonoyan . 2021. Near-Optimal Distributed Degree+1 Coloring. CoRR, abs\/2112.00604. To appear in STOC 2022 . (2021). Magn\u00fas M. Halld\u00f3rsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan. 2021. Near-Optimal Distributed Degree+1 Coloring. CoRR, abs\/2112.00604. To appear in STOC 2022. (2021)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_38"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897533"},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of the 35th Annual ACM Symposium on Theory of Computing","author":"Jayram T. S.","year":"2003","unstructured":"T. S. Jayram , Ravi Kumar , and D. Sivakumar . 2003. Two applications of information complexity . In Proceedings of the 35th Annual ACM Symposium on Theory of Computing , June 9-11, 2003 , San Diego, CA, USA, Lawrence L. Larmore and Michel X. Goemans (Eds.). ACM, 673\u2013682. T. S. Jayram, Ravi Kumar, and D. Sivakumar. 2003. Two applications of information complexity. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, Lawrence L. Larmore and Michel X. Goemans (Eds.). ACM, 673\u2013682."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90006-5"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90121-7"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.12.014"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90089-1"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(69)80057-8"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1724"},{"volume-title":"Graph colouring and the probabilistic method. 23","author":"Molloy Michael","key":"e_1_3_2_1_45_1","unstructured":"Michael Molloy and Bruce Reed . 2013. Graph colouring and the probabilistic method. 23 , Springer Science & Business Media . Michael Molloy and Bruce Reed. 2013. Graph colouring and the probabilistic method. 23, Springer Science & Business Media."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.06.004"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129769"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200759"},{"key":"e_1_3_2_1_49_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","volume":"14","author":"Parter Merav","year":"2018","unstructured":"Merav Parter . 2018 . (\u0394 + 1) Coloring in the Congested Clique Model. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , July 9-13, 2018, Prague, Czech Republic, Ioannis Chatzigiannakis, Christos Kaklamanis, D\u00e1niel Marx, and Donald Sannella (Eds.) (LIPIcs , Vol. 107). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 160:1\u2013160: 14 . Merav Parter. 2018. (\u0394 + 1) Coloring in the Congested Clique Model. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, Ioannis Chatzigiannakis, Christos Kaklamanis, D\u00e1niel Marx, and Donald Sannella (Eds.) (LIPIcs, Vol. 107). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 160:1\u2013160:14."},{"key":"e_1_3_2_1_50_1","unstructured":"Landon Rabern. 2012. A different short proof of Brooks\u2019 theorem. arXiv preprint arXiv:1205.3253. Landon Rabern. 2012. A different short proof of Brooks\u2019 theorem. arXiv preprint arXiv:1205.3253."},{"key":"e_1_3_2_1_51_1","unstructured":"Landon Rabern. 2014. Yet another proof of Brooks\u2019 theorem. arXiv preprint arXiv:1409.6812. Landon Rabern. 2014. Yet another proof of Brooks\u2019 theorem. arXiv preprint arXiv:1409.6812."},{"key":"e_1_3_2_1_52_1","volume-title":"WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings, Frank Dehne, John Iacono, and J\u00f6rg-R\u00fcdiger Sack (Eds.) (Lecture Notes in Computer Science","volume":"678","author":"Radhakrishnan Jaikumar","year":"2011","unstructured":"Jaikumar Radhakrishnan and Saswata Shannigrahi . 2011 . Streaming Algorithms for 2-Coloring Uniform Hypergraphs. In Algorithms and Data Structures - 12th International Symposium , WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings, Frank Dehne, John Iacono, and J\u00f6rg-R\u00fcdiger Sack (Eds.) (Lecture Notes in Computer Science , Vol. 6844). Springer, 667\u2013 678 . Jaikumar Radhakrishnan and Saswata Shannigrahi. 2011. Streaming Algorithms for 2-Coloring Uniform Hypergraphs. In Algorithms and Data Structures - 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings, Frank Dehne, John Iacono, and J\u00f6rg-R\u00fcdiger Sack (Eds.) (Lecture Notes in Computer Science, Vol. 6844). Springer, 667\u2013678."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/1378762.1378763"},{"key":"e_1_3_2_1_54_1","first-page":"136","article-title":"A Strengthening of Brooks\u2019 Theorem. J. Comb. Theory","volume":"76","author":"Reed Bruce A.","year":"1999","unstructured":"Bruce A. Reed . 1999 . A Strengthening of Brooks\u2019 Theorem. J. Comb. Theory , Ser. B , 76 , 2 (1999), 136 \u2013 149 . Bruce A. Reed. 1999. A Strengthening of Brooks\u2019 Theorem. J. Comb. Theory, Ser. B, 76, 2 (1999), 136\u2013149.","journal-title":"Ser. B"},{"key":"e_1_3_2_1_55_1","volume-title":"8th Scandinavian Workshop on Algorithm Theory","author":"Skulrattanakulchai San","year":"2002","unstructured":"San Skulrattanakulchai . 2002 . Delta-List Vertex Coloring in Linear Time. In Algorithm Theory - SWAT 2002 , 8th Scandinavian Workshop on Algorithm Theory , Turku, Finland , July 3-5, 2002 Proceedings. 240\u2013248. San Skulrattanakulchai. 2002. Delta-List Vertex Coloring in Linear Time. In Algorithm Theory - SWAT 2002, 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002 Proceedings. 240\u2013248."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1017\/CBO9781139519793.005","article-title":"Brooks\u2019s theorem","volume":"165","author":"Stiebitz Michael","year":"2015","unstructured":"Michael Stiebitz and Bjarne Toft . 2015 . Brooks\u2019s theorem . Topics in Chromatic Graph Theory , 165 (2015), 36 \u2013 55 . Michael Stiebitz and Bjarne Toft. 2015. Brooks\u2019s theorem. Topics in Chromatic Graph Theory, 165 (2015), 36\u201355.","journal-title":"Topics in Chromatic Graph Theory"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520005","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520005","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":56,"alternative-id":["10.1145\/3519935.3520005","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520005","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}