{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T06:36:55Z","timestamp":1767854215682,"version":"3.49.0"},"reference-count":11,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,5]],"date-time":"2006-10-05T00:00:00Z","timestamp":1160006400000},"content-version":"vor","delay-in-days":6700,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[1988,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A graph coloring algorithm that immediately colors the vertices taken from a list without looking ahead or changing colors already assigned is called \u201con\u2010line coloring.\u201d The properties of on\u2010line colorings are investigated in several classes of graphs. In many cases we find on\u2010line colorings that use no more colors than some function of the largest clique size of the graph. We show that the first fit on\u2010line coloring has an absolute performance ratio of two for the complement of chordal graphs. We prove an upper bound for the performance ratio of the first fit coloring on interval graphs. It is also shown that there are simple families resisting any on\u2010line algorithm: no on\u2010line algorithm can color all trees by a bounded number of colors.<\/jats:p>","DOI":"10.1002\/jgt.3190120212","type":"journal-article","created":{"date-parts":[[2007,6,9]],"date-time":"2007-06-09T04:11:02Z","timestamp":1181362262000},"page":"217-227","source":"Crossref","is-referenced-by-count":158,"title":["On\u2010line and first fit colorings of graphs"],"prefix":"10.1002","volume":"12","author":[{"given":"A.","family":"Gy\u00e1rf\u00e1s","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Lehel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,5]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212033"},{"key":"e_1_2_1_3_2","first-page":"57","article-title":"Strongly perfect graphs","volume":"21","author":"Berge C.","year":"1984","journal-title":"Ann. Discrete Math."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264439"},{"key":"e_1_2_1_5_2","first-page":"588","article-title":"Problem 84\u201323","volume":"5","author":"Chrobak M.","year":"1984","journal-title":"J. Algorithms"},{"key":"e_1_2_1_6_2","unstructured":"M.ChrobakandM.\u015alusarek On some packing problems related to dynamic storage allocation. Manuscript (1984)."},{"key":"e_1_2_1_7_2","unstructured":"A.Gy\u00e1rf\u00e1s On Ramsey covering numbers. Infinite and Finite Sets. North Holland Amsterdam (1975)801\u2013816."},{"key":"e_1_2_1_8_2","unstructured":"A.Gy\u00e1rf\u00e1s Problems from the World Surrounding Perfect Graphs. Computer and Automation Institute Studies 177 (1985)."},{"key":"e_1_2_1_9_2","first-page":"76","volume-title":"Graph Theory and Combinatorics","author":"McDiarmid C.","year":"1979"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/321650.321658"},{"key":"e_1_2_1_11_2","first-page":"143","article-title":"An extremal problem in recursive combinatorics","volume":"33","author":"Trotter W. T.","year":"1981","journal-title":"Congressus Numerantium"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90093-3"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.3190120212","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190120212","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T17:55:57Z","timestamp":1697910957000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190120212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,6]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1988,6]]}},"alternative-id":["10.1002\/jgt.3190120212"],"URL":"https:\/\/doi.org\/10.1002\/jgt.3190120212","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,6]]}}}