{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:32:39Z","timestamp":1787322759926,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>It is known that the First-Fit algorithm for partitioning a poset $P$ into chains uses relatively few chains when $P$ does not have two incomparable chains each of size $k$. In particular, if $P$ has width $w$, then Bosek, Krawczyk, and Szczypka [SIAM J. Discrete Math., 23 (2010), pp. 1992--1999], proved an upper bound of $ckw^{2}$ on the number of chains used by First-Fit for some constant $c$, while Joret and Milans [Order, 28 (2011), pp. 455--464] gave one of $ck^{2}w$. In this paper we prove an upper bound of the form $ckw$. This is most possible up to the value of $c$.<\/jats:p>","DOI":"10.1137\/110855806","type":"journal-article","created":{"date-parts":[[2012,7,31]],"date-time":"2012-07-31T10:56:16Z","timestamp":1343732176000},"page":"1068-1075","source":"Crossref","is-referenced-by-count":10,"title":["An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains"],"prefix":"10.1137","volume":"26","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,7,31]]},"reference":[{"key":"atyp_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-011-9197-1"},{"key":"atyp_ref2","first-page":"347","author":"Bosek B.","year":"2010","journal-title":"Proceedings of the Annual IEEE Symposium on Foundations of Computer Science"},{"key":"atyp_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2011.09.030"},{"key":"atyp_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/090753863"},{"key":"atyp_ref5","unstructured":"5.\u2002G. R. Brightwell, H. A. Kierstead, and W. T. Trotter. A Note on First Fit Coloring of Interval Graphs, manuscript, 2006."},{"key":"atyp_ref6","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1988220404871"},{"key":"atyp_ref7","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"key":"atyp_ref8","first-page":"13","author":"Downey R. G.","year":"2004","journal-title":"Berlin"},{"key":"atyp_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.08.002"},{"key":"atyp_ref11","doi-asserted-by":"crossref","first-page":"R151","DOI":"10.37236\/423","volume":"17","author":"Fijav\u017e G.","year":"2010","journal-title":"Electron. J. Combin."},{"key":"atyp_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2496(70)90062-3"},{"key":"atyp_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-010-9184-y"},{"key":"atyp_ref14","first-page":"75","author":"Kierstead H. A.","year":"1986","journal-title":"RI"},{"key":"atyp_ref15","doi-asserted-by":"publisher","DOI":"10.1137\/0401048"},{"key":"atyp_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00285-Q"},{"key":"atyp_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.05.002"},{"key":"atyp_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-008-9076-6"},{"key":"atyp_ref19","first-page":"562","volume":"2004","author":"Pemmaraju S. V.","journal-title":"Philadelphia"},{"key":"atyp_ref20","doi-asserted-by":"crossref","unstructured":"20.\u2002S. V. Pemmaraju, R. Raman, and K. Varadarajan,<i>Max-coloring and online coloring with bandwidths on interval graphs,<\/i>ACM Trans. Algorithms, July (2011), pp. 7:35:1-35:21.","DOI":"10.1145\/1978782.1978790"},{"key":"atyp_ref21","unstructured":"21.\u2002A. Schrijver,<i>Combinatorial optimization. Polyhedra and Efficiency, Vol. A<\/i> Algorithms Combin. 24, Springer-Verlag, Berlin, 2003."},{"key":"atyp_ref22","unstructured":"22.\u2002D. A. Smith,<i>The First-Fit Algorithm Uses Many Colors on Some Interval Graphs<\/i> \\newblock PhD thesis, Arizona State University, 2010."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110855806","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:25:19Z","timestamp":1787318719000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110855806"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/110855806"],"URL":"https:\/\/doi.org\/10.1137\/110855806","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}