{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T01:50:14Z","timestamp":1784425814719,"version":"3.55.0"},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2000,9]]},"abstract":"<jats:p> Graphs of clique\u2013width at most k were introduced by Courcelle, Engelfriet and Rozenberg (1993) as graphs which can be defined by k-expressions based on graph operations which use k vertex labels. <\/jats:p><jats:p> In this paper we study the clique\u2013width of perfect graph classes. <\/jats:p><jats:p> On one hand, we show that every distance\u2013hereditary graph, has clique\u2013width at most 3, and a 3\u2013expression defining it can be obtained in linear time. On the other hand, we show that the classes of unit interval and permutation graphs are not of bounded clique\u2013width. More precisely, we show that for every [Formula: see text] there is a unit interval graph I<jats:sub>n<\/jats:sub> and a permutation graph H<jats:sub>n<\/jats:sub> having n<jats:sup>2<\/jats:sup> vertices, each of whose clique\u2013width is at least n. These results allow us to see the border within the hierarchy of perfect graphs between classes whose clique\u2013width is bounded and classes whose clique\u2013width is unbounded. <\/jats:p><jats:p> Finally we show that every n\u00d7n square grid, [Formula: see text], n \u2265 3, has clique\u2013width exactly n+1. <\/jats:p>","DOI":"10.1142\/s0129054100000260","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T07:04:45Z","timestamp":1027753485000},"page":"423-443","source":"Crossref","is-referenced-by-count":169,"title":["ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES"],"prefix":"10.1142","volume":"11","author":[{"given":"MARTIN CHARLES","family":"GOLUMBIC","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Bar-Ilan University, Ramat-Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"UDI","family":"ROTICS","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Toronto, Toronto, Ontario M5S 3G4, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199805)31:3<177::AID-NET4>3.0.CO;2-C"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90004-G"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1137\/0217032"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62559-3_15"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58218-5_34"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46784-X_14"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90131-U"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/28.4.417"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054199000241"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199902)30:2<121::AID-JGT6>3.0.CO;2-1"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054100000260","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:47:00Z","timestamp":1565124420000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054100000260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,9]]},"references-count":12,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2000,9]]}},"alternative-id":["10.1142\/S0129054100000260"],"URL":"https:\/\/doi.org\/10.1142\/s0129054100000260","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,9]]}}}