{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:15:31Z","timestamp":1763468131520},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392115"},{"type":"electronic","value":"9783642392122"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39212-2_59","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T09:09:19Z","timestamp":1372756159000},"page":"681-693","source":"Crossref","is-referenced-by-count":7,"title":["Fast Distributed Coloring Algorithms for Triangle-Free Graphs"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsin-Hao","family":"Su","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"59_CR1","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley Series in Discrete Mathematics and Optimization. Wiley (2011)"},{"issue":"1","key":"59_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jctb.1999.1910","volume":"77","author":"N. Alon","year":"1999","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Coloring graphs with sparse neighborhoods. Journal of Combinatorial Theory, Series B\u00a077(1), 73\u201382 (1999)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"59_CR3","first-page":"111","volume-title":"STOC 2009","author":"L. Barenboim","year":"2009","unstructured":"Barenboim, L., Elkin, M.: Distributed (\u0394\u2009+\u20091)-coloring in linear (in \u0394) time. In: STOC 2009, pp. 111\u2013120. ACM, New York (2009)"},{"key":"59_CR4","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s00446-009-0088-2","volume":"22","author":"L. Barenboim","year":"2010","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distrib. Comput.\u00a022, 363\u2013379 (2010)","journal-title":"Distrib. Comput."},{"key":"59_CR5","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. In: FOCS 2012, pp. 321\u2013330 (October 2012)","DOI":"10.1109\/FOCS.2012.60"},{"issue":"4","key":"59_CR6","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J. Beck","year":"1991","unstructured":"Beck, J.: An algorithmic approach to the lov\u00e1sz local lemma. Random Structures & Algorithms\u00a02(4), 343\u2013365 (1991)","journal-title":"Random Structures & Algorithms"},{"issue":"3","key":"59_CR7","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0012-365X(78)90102-4","volume":"24","author":"B. Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Chromatic number, girth and maximal degree. Discrete Mathematics\u00a024(3), 311\u2013314 (1978)","journal-title":"Discrete Mathematics"},{"issue":"2-3","key":"59_CR8","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0095-8956(77)90037-5","volume":"23","author":"O.V. Borodin","year":"1977","unstructured":"Borodin, O.V., Kostochka, A.V.: On an upper bound of a graph\u2019s chromatic number, depending on the graph\u2019s degree and density. Journal of Combinatorial Theory, Series B\u00a023(2-3), 247\u2013250 (1977)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"02","key":"59_CR9","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R.L. Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society\u00a037(02), 194\u2013197 (1941)","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"issue":"1","key":"59_CR10","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0012-365X(78)90049-3","volume":"22","author":"P.A. Catlin","year":"1978","unstructured":"Catlin, P.A.: A bound on the chromatic number of a graph. Discrete Math.\u00a022(1), 81\u201383 (1978)","journal-title":"Discrete Math."},{"key":"59_CR11","unstructured":"Elkin, M.: Personal communication"},{"issue":"1","key":"59_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1006\/jagm.2000.1097","volume":"37","author":"D.A. Grable","year":"2000","unstructured":"Grable, D.A., Panconesi, A.: Fast distributed algorithms for Brooks-Vizing colorings. Journal of Algorithms\u00a037(1), 85\u2013120 (2000)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"59_CR13","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1017\/S0963548301004758","volume":"10","author":"P.E. Haxell","year":"2001","unstructured":"Haxell, P.E.: A note on vertex list colouring. Comb. Probab. Comput.\u00a010(4), 345\u2013347 (2001)","journal-title":"Comb. Probab. Comput."},{"key":"59_CR14","unstructured":"Jamall, M.S.: A Brooks\u2019 Theorem for Triangle-Free Graphs. ArXiv e-prints (2011)"},{"key":"59_CR15","unstructured":"Jamall, M.S.: A Coloring Algorithm for Triangle-Free Graphs. ArXiv e-prints (2011)"},{"key":"59_CR16","unstructured":"Jamall, M.S.: Coloring Triangle-Free Graphs and Network Games. Dissertation. University of California, San Diego (2011)"},{"key":"59_CR17","unstructured":"Jensen, T.R., Toft, B.: Graph coloring problems. Wiley-Interscience series in discrete mathematics and optimization. Wiley (1995)"},{"key":"59_CR18","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1017\/S0963548300001528","volume":"4","author":"J.H. Kim","year":"1995","unstructured":"Kim, J.H.: On brooks\u2019 theorem for sparse graphs. Combinatorics. Probability and Computing\u00a04, 97\u2013132 (1995)","journal-title":"Combinatorics. Probability and Computing"},{"key":"59_CR19","first-page":"23","volume":"30","author":"A.V. Kostochka","year":"1977","unstructured":"Kostochka, A.V., Mazuronva, N.P.: An inequality in the theory of graph coloring. Metody Diskret. Analiz.\u00a030, 23\u201329 (1977)","journal-title":"Metody Diskret. Analiz."},{"key":"59_CR20","first-page":"138","volume-title":"SPAA 2009","author":"F. Kuhn","year":"2009","unstructured":"Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: SPAA 2009, pp. 138\u2013144. ACM, New York (2009)"},{"issue":"1","key":"59_CR21","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0012-365X(78)90147-4","volume":"21","author":"J. Lawrence","year":"1978","unstructured":"Lawrence, J.: Covering the vertex set of a graph with subgraphs of smaller degree. Discrete Mathematics\u00a021(1), 61\u201368 (1978)","journal-title":"Discrete Mathematics"},{"issue":"1","key":"59_CR22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput.\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"key":"59_CR23","doi-asserted-by":"crossref","unstructured":"Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics. Springer (2001)","DOI":"10.1007\/978-3-642-04016-0"},{"issue":"2","key":"59_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1667053.1667060","volume":"57","author":"R.A. Moser","year":"2010","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general lov\u00e1sz local lemma. J. ACM\u00a057(2), 11:1\u201311:15 (2010)","journal-title":"J. ACM"},{"issue":"2","key":"59_CR25","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A. Panconesi","year":"1996","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. Journal of Algorithms\u00a020(2), 356\u2013374 (1996)","journal-title":"Journal of Algorithms"},{"key":"59_CR26","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"2","key":"59_CR27","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1002\/(SICI)1097-0118(199906)31:2<149::AID-JGT8>3.0.CO;2-#","volume":"31","author":"B. Reed","year":"1999","unstructured":"Reed, B.: The list colouring constants. Journal of Graph Theory\u00a031(2), 149\u2013153 (1999)","journal-title":"Journal of Graph Theory"},{"issue":"1","key":"59_CR28","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1006\/jctb.2002.2110","volume":"86","author":"B. Reed","year":"2002","unstructured":"Reed, B., Sudakov, B.: Asymptotically the list colouring constants are 1. J. Comb. Theory Ser. B\u00a086(1), 27\u201337 (2002)","journal-title":"J. Comb. Theory Ser. B"},{"key":"59_CR29","unstructured":"Rubinfeld, R., Tamir, G., Vardi, S., Xie, N.: Fast local computation algorithms. In: ICS 2011, pp. 223\u2013238 (2011)"},{"key":"59_CR30","first-page":"257","volume-title":"PODC 2010","author":"J. Schneider","year":"2010","unstructured":"Schneider, J., Wattenhofer, R.: A new technique for distributed symmetry breaking. In: PODC 2010, pp. 257\u2013266. ACM, New York (2010)"},{"issue":"144)","key":"59_CR31","first-page":"117","volume":"23","author":"V.G. Vizing","year":"1968","unstructured":"Vizing, V.G.: Some unsolved problems in graph theory. Uspekhi Mat. Nauk\u00a023(6(144)), 117\u2013134 (1968)","journal-title":"Uspekhi Mat. Nauk"},{"issue":"1","key":"59_CR32","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1017\/S0963548301004898","volume":"11","author":"H. Vu Van","year":"2002","unstructured":"Van Vu, H.: A general upper bound on the list chromatic number of locally sparse graphs. Comb. Probab. Comput.\u00a011(1), 103\u2013111 (2002)","journal-title":"Comb. Probab. Comput."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39212-2_59","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T05:14:46Z","timestamp":1557897286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39212-2_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392115","9783642392122"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39212-2_59","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}