{"created":"2021-03-01T06:20:10.539543+00:00","id":13168,"links":{},"metadata":{"_buckets":{"deposit":"a6fe5e49-272e-405f-8c48-792f34f18b34"},"_deposit":{"id":"13168","owners":[],"pid":{"revision_id":0,"type":"depid","value":"13168"},"status":"published"},"_oai":{"id":"oai:nagoya.repo.nii.ac.jp:00013168","sets":["320:321:322"]},"author_link":["41552","41553","41554"],"item_10_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2003-05-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicPageEnd":"1051","bibliographicPageStart":"1046","bibliographicVolumeNumber":"E86-A","bibliographic_titles":[{"bibliographic_title":"IEICE transactions on fundamentals of electronics, communications and computer sciences","bibliographic_titleLang":"en"}]}]},"item_10_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"Karger, Motwani and Sudan presented a graph coloring algorithm based on semidefinite programming, which colors any k-colorable graph with maximum degree Δ using Õ(Δ^1-2/k) colors. This algorithm leads to an algorithm for k-colorable graph using Õ(n ^1-3/^(k+1)) colors. This improved Wigderson's algorithm, which uses O(n^1-1/^(k-1)) colors, containing as a subroutine an algorithm using (Δ+1) colors for graphs with maximum degree Δ. It is easy to imagine that an algorithm which uses less colors in terms of Δ leads to an algorithm which uses less colors in terms of n. In this paper, we consider this influence assuming that we have an algorithm which uses Õ(Δ^1-x/k) colors for 2