{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T17:14:53Z","timestamp":1781630093420,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"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":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316393","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"355-364","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Towards the locality of Vizing\u2019s theorem"],"prefix":"10.1145","author":[{"given":"Hsin-Hao","family":"Su","sequence":"first","affiliation":[{"name":"Boston College, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hoa T.","family":"Vu","sequence":"additional","affiliation":[{"name":"Boston College, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Noga Alon L\u00e1szl\u00f3 Babai and Alon Itai. 1986.  Noga Alon L\u00e1szl\u00f3 Babai and Alon Itai. 1986."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_3_1","unstructured":"Eshrat Arjomandi. 1982.  Eshrat Arjomandi. 1982."},{"key":"e_1_3_2_1_4_1","volume-title":"INFOR: Information Systems and Operational Research 20, 2","author":"Graph An Efficient","year":"1982","unstructured":"An Efficient Algorithm for Colouring the Edges of a Graph With ( \u2206 + 1) Colours . INFOR: Information Systems and Operational Research 20, 2 ( 1982 ), 82\u2013101. An Efficient Algorithm for Colouring the Edges of a Graph With ( \u2206 + 1) Colours. INFOR: Information Systems and Operational Research 20, 2 (1982), 82\u2013101."},{"key":"e_1_3_2_1_5_1","unstructured":"Leonid Barenboim. 2015.  Leonid Barenboim. 2015."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767410"},{"key":"e_1_3_2_1_7_1","unstructured":"Leonid Barenboim and Michael Elkin. 2010.  Leonid Barenboim and Michael Elkin. 2010."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212769"},{"key":"e_1_3_2_1_10_1","unstructured":"L. Barenboim M. Elkin and F. Kuhn. 2014.  L. Barenboim M. Elkin and F. Kuhn. 2014."},{"key":"e_1_3_2_1_11_1","volume-title":"72\u201395","author":"Time Distributed","year":"2014","unstructured":"Distributed ( \u2206 + 1)-Coloring in Linear (in \u2206) Time . SIAM J. Comput . 43, 1 ( 2014 ), 72\u201395 . Distributed ( \u2206 + 1)-Coloring in Linear (in \u2206) Time. SIAM J. Comput. 43, 1 (2014), 72\u201395."},{"key":"e_1_3_2_1_12_1","unstructured":"L. Barenboim M. Elkin S. Pettie and J. Schneider. 2016.  L. Barenboim M. Elkin S. Pettie and J. Schneider. 2016."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_1_14_1","unstructured":"Y.-J. Chang Q. He W. Li S. Pettie and J. Uitto. 2018.  Y.-J. Chang Q. He W. Li S. Pettie and J. Uitto. 2018."},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2633\u20132652","author":"The","unstructured":"The complexity of distributed edge coloring with small palettes . In Proceedings 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2633\u20132652 . The complexity of distributed edge coloring with small palettes. In Proceedings 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2633\u20132652."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188964"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611465"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310552"},{"key":"e_1_3_2_1_19_1","unstructured":"STOC \u201919 June 23\u201326 2019 Phoenix AZ USA Hsin-Hao Su and Hoa T. Vu  STOC \u201919 June 23\u201326 2019 Phoenix AZ USA Hsin-Hao Su and Hoa T. Vu"},{"key":"e_1_3_2_1_20_1","unstructured":"Devdatt Dubhashi David A Grable and Alessandro Panconesi. 1998.  Devdatt Dubhashi David A Grable and Alessandro Panconesi. 1998."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00022-X"},{"key":"e_1_3_2_1_22_1","unstructured":"Michael Elkin Seth Pettie and Hsin-Hao Su. 2015.  Michael Elkin Seth Pettie and Hsin-Hao Su. 2015."},{"key":"e_1_3_2_1_23_1","volume-title":"Symp. on Discrete Algorithms (SODA). SIAM, 355\u2013370","unstructured":"( 2 \u2206\u22121)-edge-coloring is much easier than maximal matching in the distributed setting . In Symp. on Discrete Algorithms (SODA). SIAM, 355\u2013370 . (2 \u2206\u22121)-edge-coloring is much easier than maximal matching in the distributed setting. In Symp. on Discrete Algorithms (SODA). SIAM, 355\u2013370."},{"key":"e_1_3_2_1_24_1","unstructured":"Manuela Fischer Mohsen Ghaffari and Fabian Kuhn. 2017.  Manuela Fischer Mohsen Ghaffari and Fabian Kuhn. 2017."},{"key":"e_1_3_2_1_25_1","volume-title":"Hypergraph Maximal Matching. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS). 180\u2013191","author":"Deterministic Distributed","unstructured":"Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS). 180\u2013191 . Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS). 180\u2013191."},{"key":"e_1_3_2_1_26_1","unstructured":"Pierre Fraigniaud Marc Heinrich and Adrian Kosowski. 2016.  Pierre Fraigniaud Marc Heinrich and Adrian Kosowski. 2016."},{"key":"e_1_3_2_1_27_1","volume-title":"Conflict Coloring. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS).","author":"Local","unstructured":"Local Conflict Coloring. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS). to appear, arXiv:1511.01287. Local Conflict Coloring. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS). to appear, arXiv:1511.01287."},{"key":"e_1_3_2_1_28_1","volume-title":"Technical Report TRECIS-8501, Tohoku University","author":"Gabow H. N.","year":"1985","unstructured":"H. N. Gabow , T. Nishizeki , O. Kariv , D. Leven , and O. Terada . 1985 . Algorithms for Edge-Coloring Graphs . Technical Report TRECIS-8501, Tohoku University (1985). H. N. Gabow, T. Nishizeki, O. Kariv, D. Leven, and O. Terada. 1985. Algorithms for Edge-Coloring Graphs. Technical Report TRECIS-8501, Tohoku University (1985)."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.12.006"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_1_31_1","volume-title":"Proc. of the Int\u2019l Symp. on Dist. Comp. (DISC). 1\u201315","author":"Ghaffari Mohsen","year":"2017","unstructured":"Mohsen Ghaffari , Juho Hirvonen , Fabian Kuhn , Yannic Maus , Jukka Suomela , and Jara Uitto . 2017 . Improved Distributed Degree Splitting and Edge Coloring . In Proc. of the Int\u2019l Symp. on Dist. Comp. (DISC). 1\u201315 . Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. 2017. Improved Distributed Degree Splitting and Edge Coloring. In Proc. of the Int\u2019l Symp. on Dist. Comp. (DISC). 1\u201315."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188906"},{"key":"e_1_3_2_1_33_1","unstructured":"Mohsen Ghaffari and Hsin-Hao Su. 2017.  Mohsen Ghaffari and Hsin-Hao Su. 2017."},{"key":"e_1_3_2_1_34_1","volume-title":"Orientations. In Proc. 28th ACM-SIAM Symposium on Discrete Algorithms (SODA). 2505\u20132523","author":"Splitting Distributed Degree","unstructured":"Distributed Degree Splitting , Edge Coloring , and Orientations. In Proc. 28th ACM-SIAM Symposium on Discrete Algorithms (SODA). 2505\u20132523 . Distributed Degree Splitting, Edge Coloring, and Orientations. In Proc. 28th ACM-SIAM Symposium on Discrete Algorithms (SODA). 2505\u20132523."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90169-4"},{"key":"e_1_3_2_1_36_1","unstructured":"A. V. Goldberg S. A. Plotkin and G. E. Shannon. 1988.  A. V. Goldberg S. A. Plotkin and G. E. Shannon. 1988."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401044"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178120"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00064-2"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90041-S"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129769"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.018"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019126406181"},{"key":"e_1_3_2_1_49_1","volume-title":"Vu","author":"Su Hsin-Hao","year":"2019","unstructured":"Hsin-Hao Su and Hoa T . Vu . 2019 . Towards the Locality of Vizing\u2019s Theorem. CoRR abs\/1901.00479 (2019). arXiv: 1901.00479 http:\/\/arxiv.org\/abs\/1901.00479 Hsin-Hao Su and Hoa T. Vu. 2019. Towards the Locality of Vizing\u2019s Theorem. CoRR abs\/1901.00479 (2019). arXiv: 1901.00479 http:\/\/arxiv.org\/abs\/1901.00479"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316393","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316393","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316393"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":49,"alternative-id":["10.1145\/3313276.3316393","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316393","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}