{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T03:28:08Z","timestamp":1784086088057,"version":"3.55.0"},"reference-count":16,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1999,9]]},"abstract":"<jats:p>Babel and Olariu (1995) introduced the class of (q, t) graphs in which every set of q vertices has at most t distinct induced P<jats:sub>4<\/jats:sub>s. Graphs of clique-width 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. In this paper we study the clique\u2013width of the (q, t) graphs, for almost all possible combinations of q and t. On one hand we show that every (q, q - 3) graph for q \u2265 7, has clique\u2013width \u2264 q and a q\u2013expression defining it can be obtained in linear time. On the other hand we show that the class of (q, q - 3) graphs for 4 \u2264 q \u2264 6 and the class of (q, q - 1) graphs for q \u2265 4 are not of bounded clique-width.<\/jats:p>","DOI":"10.1142\/s0129054199000241","type":"journal-article","created":{"date-parts":[[2003,1,22]],"date-time":"2003-01-22T12:24:14Z","timestamp":1043238254000},"page":"329-348","source":"Crossref","is-referenced-by-count":62,"title":["ON THE CLIQUE\u2013WIDTH OF GRAPH WITH FEW P<sub>4<\/sub>'S"],"prefix":"10.1142","volume":"10","author":[{"given":"J. A.","family":"MAKOWSKY","sequence":"first","affiliation":[{"name":"Department of Computer Science, Technion-Israel Institute of Technology, 32000 Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"U.","family":"ROTICS","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Technion-Israel Institute of Technology, 32000 Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.2.170"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1007\/10692760_27"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)90120-7"},{"key":"p_7","first-page":"6","volume":"4","author":"Courcelle B.","year":"1993","journal-title":"J. Comput. System Sci."},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017474"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90013-5"},{"key":"p_11","first-page":"1","volume":"1517","author":"Courcelle B.","year":"1998","journal-title":"Computer Science"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/147\/01200"},{"key":"p_16","doi-asserted-by":"crossref","first-page":"17","DOI":"10.46298\/dmtcs.232","volume":"1","author":"Giakoumakis V.","year":"1997","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00220-4"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1002\/sapm198981179"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1137\/0221027"},{"key":"p_20","first-page":"5","volume":"3","author":"Jamison B.","year":"1992","journal-title":"Discrete Appl. Math."},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00016-P"},{"key":"p_22","first-page":"1","volume":"6","author":"Jamison B.","year":"1995","journal-title":"Discrete Appl. Math."},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90026-4"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054199000241","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T21:18:17Z","timestamp":1704748697000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054199000241"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,9]]},"references-count":16,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[1999,9]]}},"alternative-id":["10.1142\/S0129054199000241"],"URL":"https:\/\/doi.org\/10.1142\/s0129054199000241","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,9]]}}}