{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T08:50:39Z","timestamp":1781686239448,"version":"3.54.5"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1007\/bf01200759","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T12:13:34Z","timestamp":1108728814000},"page":"255-280","source":"Crossref","is-referenced-by-count":41,"title":["The local nature of ?-coloring and its algorithmic applications"],"prefix":"10.1007","volume":"15","author":[{"given":"Alessandro","family":"Panconesi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A. V. Goldberg, M. Luby, andS. A. Plotkin: Network decomposition locality in distributed computation, in:Proceedings of the IEEE Symposium on Foundations of Computer Science, (1989), 364?369.","DOI":"10.1109\/SFCS.1989.63504"},{"key":"CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-9967-7","volume-title":"Graph Theory","author":"B. Bollob\ufffds","year":"1979","unstructured":"B. Bollob\ufffds:Graph Theory, Springer Verlag, New York, 1979."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R. L. Brooks","year":"1941","unstructured":"R. L. Brooks: On colouring the nodes of a network,Proc. Cambridge Phil. Soc. 37 (1941), 194?197.","journal-title":"Proc. Cambridge Phil. Soc."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R. Cole","year":"1986","unstructured":"R. Cole, andU. Vishkin: Deterministic coin tossing with applications to optimal parallel list ranking,Information and Control 70 (1986), 32?53.","journal-title":"Information and Control"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1137\/0401044","volume":"1","author":"A. V. Goldberg","year":"1989","unstructured":"A. V. Goldberg, S. A. Plotkin, andG. E. Shannon: Parallel symmetry-breaking in sparse graphs,SIAM J. Disc. Math. 1 (1989), 434?446.","journal-title":"SIAM J. Disc. Math."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1137\/0403008","volume":"3","author":"P. Hajnal","year":"1990","unstructured":"P. Hajnal, andE. Szemer\ufffddi: Brooks coloring in parallel,SIAM. J. Disc. Math. 3 (1990), 74?80.","journal-title":"SIAM. J. Disc. Math."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0196-6774(88)90006-5","volume":"9","author":"M. Krachmer","year":"1988","unstructured":"M. Krachmer, andJ. Naor: A faster parallel algorithm to color a graphy with ? colors,Journal of Algorithms 9 (1988), 83?91.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"CR8","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0304-3975(89)90121-7","volume":"68","author":"H. J. Karloff","year":"1989","unstructured":"H. J. Karloff: An NC-algorithm for Brooks' theorem,Theoretical Computer Science 68(1) (1989), 89?103.","journal-title":"Theoretical Computer Science"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"R. M. Karp: Probabilistic recurrence relations, in:Proceedings of the ACM Symposium on Theory of Computing (1991), 190?197.","DOI":"10.1145\/103418.103443"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TC.1981.6312171","volume":"30","author":"G. F. Lev","year":"1981","unstructured":"G. F. Lev, N. Pippenger, andL. G. Valiant: A fast parallel algorithm for routing in permutation networks,IEEE Transactions on Computers 30 (1981), 93?100.","journal-title":"IEEE Transactions on Computers"},{"issue":"1","key":"CR11","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"N. Linial: Locality in distributed graph algorithms,SIAM J. Comput. 21(1) (1992), 193?201.","journal-title":"SIAM J. Comput."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1016\/0022-0000(93)90033-S","volume":"47","author":"M. Luby","year":"1993","unstructured":"M. Luby: Removing randomness in parallel computation without a processor penalty,Journal of Computer and System Sciences,47 (1993), 250?286.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"A. Panconesi, andA. Srinivasan: Improved distributed algorithm for coloring and network decomposition problems, in:Proceedings of the ACM Symposium on Theory of Computing (1992), 581?592.","DOI":"10.1145\/129712.129769"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200759.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01200759\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T20:57:46Z","timestamp":1586120266000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01200759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["BF01200759"],"URL":"https:\/\/doi.org\/10.1007\/bf01200759","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}