{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T15:42:11Z","timestamp":1770738131757,"version":"3.49.0"},"reference-count":22,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[1989,5,1]],"date-time":"1989-05-01T00:00:00Z","timestamp":609984000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8843,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Mathematics"],"published-print":{"date-parts":[[1989,5]]},"DOI":"10.1016\/0012-365x(89)90096-4","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:43:43Z","timestamp":1027640623000},"page":"319-325","source":"Crossref","is-referenced-by-count":92,"title":["An on-line graph coloring algorithm with sublinear performance ratio"],"prefix":"10.1016","volume":"75","author":[{"given":"L\u00e1szl\u00f3","family":"Lov\u00e1sz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"W.T.","family":"Trotter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0012-365X(89)90096-4_BIB1","doi-asserted-by":"crossref","first-page":"469","DOI":"10.2307\/2272247","article-title":"Effective coloration","volume":"41","author":"Bean","year":"1976","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0012-365X(89)90096-4_BIB2","unstructured":"J.L. Bentley and C.C. McGeoch, Worst-case analyses of self-organizing sequential search heuristics, Communications of ACM, to appear."},{"key":"10.1016\/0012-365X(89)90096-4_BIB3","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1137\/0208007","article-title":"Heuristics that dynamically organize data structures","volume":"8","author":"Bitner","year":"1979","journal-title":"SIAM J. Comp."},{"key":"10.1016\/0012-365X(89)90096-4_BIB4","first-page":"373","article-title":"An online algorithm for metrical task systems","author":"Borodin","year":"1987","journal-title":"Proc. 19th Annual ACM Symp. on Theory of Computing"},{"key":"10.1016\/0012-365X(89)90096-4_BIB5","series-title":"Discrete Algorithms and Complexity","article-title":"Dynamic search in graphs","author":"Chung","year":"1987"},{"key":"10.1016\/0012-365X(89)90096-4_BIB6","unstructured":"F.R.K. Chung, R.L. Graham and M. Saks, A dynamic location problem for graphs, Preprint."},{"key":"10.1016\/0012-365X(89)90096-4_BIB7","unstructured":"(a) Gy\u00e1rf\u00e1s and J. Lehel, On-line and first-fit colorings of graphs, J. Graph Theory, to appear."},{"key":"10.1016\/0012-365X(89)90096-4_BIB8","first-page":"169","article-title":"Toward self-organizing search heuristics","author":"Gonnet","year":"1979","journal-title":"Proc. 20th IEEE Symp. Foundations of Comp. Sci."},{"key":"10.1016\/0012-365X(89)90096-4_BIB9","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0203025","article-title":"Worst case performance bounds for simple one-dimensional bin packing algorithms","volume":"3","author":"Johnson","year":"1974","journal-title":"SIAM J. Computing"},{"key":"10.1016\/0012-365X(89)90096-4_BIB10","first-page":"244","article-title":"Competitive snoopy catching","author":"Karlin","year":"1986","journal-title":"Proc. 27th IEEE Symp. Foundations of Comp. Sci."},{"key":"10.1016\/0012-365X(89)90096-4_BIB11","first-page":"63","article-title":"An effective version of Dilworth's theorem","volume":"268","author":"Kierstead","year":"1981","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0012-365X(89)90096-4_BIB12","doi-asserted-by":"crossref","unstructured":"H.A. Kierstead, The linearity of first-fit colorings of interval graphs, SIAM J. on Discrete Math., to appear.","DOI":"10.1137\/0401048"},{"key":"10.1016\/0012-365X(89)90096-4_BIB13","doi-asserted-by":"crossref","unstructured":"H.A. Kierstead, G.F. McNulty and W.T. Trotter, A theory of recursive dimension for ordered sets, Order 1, 67-82.","DOI":"10.1007\/BF00396274"},{"key":"10.1016\/0012-365X(89)90096-4_BIB14","first-page":"143","article-title":"An extremal problem in recursive combinatorics","volume":"33","author":"Kierstead","year":"1981","journal-title":"Congressus Numerantium"},{"key":"10.1016\/0012-365X(89)90096-4_BIB15","article-title":"Competitive algorithms for on-line problems","author":"Manasse","year":"1988","journal-title":"Proc. 20th Annual Symp. on Theory of Computing"},{"key":"10.1016\/0012-365X(89)90096-4_BIB16","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/359997.360000","article-title":"On self-organizing sequential search heuristics","volume":"19","author":"Rivest","year":"1976","journal-title":"CACM"},{"key":"10.1016\/0012-365X(89)90096-4_BIB17","series-title":"Graphs and Order","first-page":"467","article-title":"Recursion theoretic aspects of graphs and order","author":"Schmerl","year":"1984"},{"key":"10.1016\/0012-365X(89)90096-4_BIB18","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","article-title":"Amortized efficiency of list update and paging rules","volume":"23","author":"Sleator","year":"1985","journal-title":"CACM"},{"key":"10.1016\/0012-365X(89)90096-4_BIB19","unstructured":"M. Szegedy, personal communication."},{"key":"10.1016\/0012-365X(89)90096-4_BIB20","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","article-title":"Amortized computational complexity","volume":"6","author":"Tarjan","year":"1985","journal-title":"SIAM J. Alg. Disc. Methods"},{"key":"10.1016\/0012-365X(89)90096-4_BIB21","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1145\/2157.2158","article-title":"Improving the performance guarantee for approximate graph coloring","volume":"30","author":"Wigderson","year":"1983","journal-title":"J. ACM"},{"key":"10.1016\/0012-365X(89)90096-4_BIB22","first-page":"202","article-title":"Problem no. 4","volume":"13","author":"Woodall","year":"1974"}],"container-title":["Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0012365X89900964?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0012365X89900964?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T01:50:39Z","timestamp":1555120239000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0012365X89900964"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,5]]},"references-count":22,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1989,5]]}},"alternative-id":["0012365X89900964"],"URL":"https:\/\/doi.org\/10.1016\/0012-365x(89)90096-4","relation":{},"ISSN":["0012-365X"],"issn-type":[{"value":"0012-365X","type":"print"}],"subject":[],"published":{"date-parts":[[1989,5]]}}}