{"entities":{"Q1406046":{"pageid":1416786,"ns":120,"title":"Item:Q1406046","lastrevid":48171031,"modified":"2026-01-03T20:47:22Z","type":"item","id":"Q1406046","labels":{"en":{"language":"en","value":"On variations of \\(P_{4}\\)-sparse graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1977916"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$3AEF33A9-5148-4391-A431-66D5B4616F84","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e781f9ad6c09a498f262b44a28e9371f6e5fdbd0","datavalue":{"value":{"text":"On variations of \\(P_{4}\\)-sparse graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1406046$65CA232F-8AEF-467F-A9DE-14CF283B59DF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"df359c90f6974b65545dcb7a5140abecc0e57bd6","datavalue":{"value":"1022.05069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406046$15DB0730-A823-42AC-BDC0-8B37CD19198E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4269e90dd4f481ee5400c5e38a67fbe1f99bd356","datavalue":{"value":"10.1016/S0166-218X(03)00180-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406046$14F29BAA-FE97-4E3C-BF12-F6D4F4AB0D8E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb68d9de22321af7fb543db220c0a16a741857c","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$F5D23CCE-EADC-4C65-A162-515CE899A605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1cf9debe45e382f5f77b3553301ae0391bc889d","datavalue":{"value":{"entity-type":"item","numeric-id":222633,"id":"Q222633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$CD2E42AC-1753-4B36-857D-35766A6CD6A5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$8D414DBC-073E-42F6-9317-B9CCE2F5A106","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5a3bd22b3255d28cafbe1a32be16f369f6f38fa5","datavalue":{"value":{"time":"+2003-09-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1406046$E8308B9B-1A76-4F46-93A9-0DE5B09FD56C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"48a31fd8b57e95d686893cdde8ebb8becf251a34","datavalue":{"value":"A graph is \\(P_4\\)-sparse if every subgraph induced by five vertices contains at most one \\(P_4\\). Ho\u00e0ng, who introduced this class, characterised \\(P_4\\)-sparse graphs by their prime graphs under modular decomposition. A \\(P_4\\)-extension is a graph on five vertices containing a \\(P_4\\). \\(P_4\\)-sparse graphs and several superclasses defined by forbidden \\(P_4\\)-extensions have bounded clique-width. This allows linear-time algorithms for all problems expressible in LinEMSOL(\\(\\tau_{1,\\text{ L}}\\)) when restricted to such a class, see \\textit{B. Courcelle, J. A. Makowsky} and \\textit{U. Rotics} [Theory Comput. Syst. 33, 125-150 (2000; Zbl 1009.68102)]. The authors classify all superclasses of \\(P_4\\)-sparse graphs defined by forbidding one \\(P_4\\)-extension into classes of bounded clique-width and classes of unbounded clique-width. A similar classification of classes defined by up to three forbidden \\(P_4\\)-extensions was given in a related paper additionally authored by \\textit{F. F. Dragan} and \\textit{H.-O. Le} [Lect. Notes Comput. Sci. 2573, 57-67 (2002; Zbl 1022.68090)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406046$F24D5FE5-21BD-409F-8BA2-BE721766463E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406046$E9C87D37-B7CF-4877-8D27-D08EB724D666","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4f11c1e3639d6fa8c11222ce76ab5e96dc468741","datavalue":{"value":"1977916","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1406046$1311AC0F-C3F3-4C49-853E-47E42D58F520","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad18c77d3177a14fcc58df9994d503238b5aaa98","datavalue":{"value":"\\(P_4\\)-spares graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406046$59B369F6-A7E3-4F6B-87FD-42F93B7B3032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6f2932b49c099044c16ddf17676c388fc81a8aa","datavalue":{"value":"prime graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406046$87AA2DB1-DA77-4CC0-A8E0-AA6FB99CE74B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5eb03826ecb9d862c3a8c13a3c8eb36c4bc27ecd","datavalue":{"value":"clique-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406046$1A748691-D7E0-4A2B-A95E-F4A86B888DB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406046$9BB5BEDF-9C32-4C81-AEE7-9D6DD53D2120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d16b11223dd43ac9feeeb5b11a98ef1a7a06ae9a","datavalue":{"value":"monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406046$1FEE14CB-6B7E-406B-8C33-117942AE01CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6bd66b264b999e9a869b6fb926495103852b05c","datavalue":{"value":"\\(P_4\\)-extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1406046$CE41C975-AD9D-4BD6-9BE6-4CA41FBEEB09","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$EA8F1BDE-1117-44B4-AF15-FB2A38FC27C9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"82c782b972b963ba01b130cb0496633bbdd0a21a","datavalue":{"value":{"entity-type":"item","numeric-id":1302141,"id":"Q1302141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$AA480349-B40B-4E83-8B12-731CA9FC00C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24ab94925d77f68bbba9bb500216729d0045622e","datavalue":{"value":{"entity-type":"item","numeric-id":1363736,"id":"Q1363736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$4121D80D-F320-467E-9ECB-F7B7F19F4029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ece2274710d7fa0f710c2bb5b2ad8f4939b1c82","datavalue":{"value":{"entity-type":"item","numeric-id":1408811,"id":"Q1408811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$B25EB75D-6B47-41A0-B567-A933CFD698C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"282d88b529308441c287f6c692de7afeae122bdc","datavalue":{"value":{"entity-type":"item","numeric-id":4243764,"id":"Q4243764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$79551B29-3979-4830-825B-ACB0F63892B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$F6E0B5F5-0C51-4116-A296-1513A5AF2D0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01daeab766d175bddc9f50c88df891bc3bb25b36","datavalue":{"value":{"entity-type":"item","numeric-id":3676177,"id":"Q3676177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$E0D75A9E-85AA-4A91-B67C-90323D9008FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3edc2fe01664e7ae5dbedc60a81011b311142a1b","datavalue":{"value":{"entity-type":"item","numeric-id":3694709,"id":"Q3694709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$20DA85C0-48CA-4ADC-B653-8B348B751AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7af2c5eca3bd22f8693a9ef2542f46a220d3edf1","datavalue":{"value":{"entity-type":"item","numeric-id":2366278,"id":"Q2366278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$5092CA3F-1EBA-4ACE-8CB2-558678D0E6F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751c6211e64b51a8e1aca9a77a723434c8cf281c","datavalue":{"value":{"entity-type":"item","numeric-id":4232773,"id":"Q4232773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$92211669-8518-459C-9E16-73B4F0446F06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"211530a7d66720062b60e82cf130f31beea4a662","datavalue":{"value":{"entity-type":"item","numeric-id":1975365,"id":"Q1975365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$A519CEDF-D1B6-4277-8C95-A40844F91860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed91ed0176924a73cbecba9388f8a04535563e10","datavalue":{"value":{"entity-type":"item","numeric-id":4954442,"id":"Q4954442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$8F34E4F6-13F0-4FF8-800E-EEA86F4BA77C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bd9545135d8eb802bd4c19148d6cda41510d602","datavalue":{"value":{"entity-type":"item","numeric-id":2775895,"id":"Q2775895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$7BC1E43B-D409-4E34-821C-8F8478C90D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8add4627ebed45e331231c9fcb96d24b9b77ef2d","datavalue":{"value":{"entity-type":"item","numeric-id":4193514,"id":"Q4193514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$BAEA9811-8C9A-463A-811E-8F5B6C367DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f0bbee70e974bce02bd0ec590b8a15aec2e7266","datavalue":{"value":{"entity-type":"item","numeric-id":3836509,"id":"Q3836509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$E3BFAC41-E5DB-46E9-88F0-D4D5CEF65A26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f21d83fa066310af6b79fc5d3e4969e1c27e6aec","datavalue":{"value":{"entity-type":"item","numeric-id":1390873,"id":"Q1390873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$C452C65B-E2F6-43F1-924D-2A2E7136B6B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdf52250f133edaea359c7055d24ec04113ee167","datavalue":{"value":{"entity-type":"item","numeric-id":5895304,"id":"Q5895304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$6BF3E520-915D-4186-9178-01692356C1DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbe76e0762ef700f0ca9d7f733f0d5ad37484351","datavalue":{"value":{"entity-type":"item","numeric-id":3831058,"id":"Q3831058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$69EDBC51-20C7-4FB6-9E13-DE36B7CBB1D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0aae757a56df0e1aae621c1729d15bd0c25fda68","datavalue":{"value":{"entity-type":"item","numeric-id":3990660,"id":"Q3990660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$0CA6CC20-625E-4DC6-8F0F-E1C6457BD298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3b2998788fd5c6bb689ab64483e3a026a3e293a","datavalue":{"value":{"entity-type":"item","numeric-id":1183332,"id":"Q1183332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$CDEEA26B-6B5C-46E5-8192-7837A93FB4C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4b08cd74d329e3f535b2242cb35c72b76385dec","datavalue":{"value":{"entity-type":"item","numeric-id":1897361,"id":"Q1897361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$8C1F767F-57C6-47F1-BBB5-7B831E3EDECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cfcd8d613906535ebdafef3a5dd83e49107cccf","datavalue":{"value":{"entity-type":"item","numeric-id":5249008,"id":"Q5249008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$9DBF867E-FF3A-4EFF-9792-662D197A20BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e405b7fbda3f49c85188dd1e8eaf0b9f0a8ade2b","datavalue":{"value":{"entity-type":"item","numeric-id":1301738,"id":"Q1301738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$981B8A60-51C4-4FED-B686-76E2679BBBD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14f316bda1db96a4382c7a9143b182e390b18612","datavalue":{"value":{"entity-type":"item","numeric-id":3663349,"id":"Q3663349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1406046$4146B1A3-ECD9-473A-967E-B56AC6B37C38","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79ba6d5243eb654e25f1ef41d591e19e588f8e15","datavalue":{"value":{"entity-type":"item","numeric-id":1390873,"id":"Q1390873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1c395f27dedec825dd2f7b5655235dac1cf5388","datavalue":{"value":{"amount":"+0.8253439664840698","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1406046$E9DDBE17-A8D0-4E32-AEC6-E8E6E0708FAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1944452450a79df40eba5d56c0dbc946d0083c3d","datavalue":{"value":{"entity-type":"item","numeric-id":629355,"id":"Q629355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"476f0e879948e3f7fe1fbf19b230440a18e0f5cc","datavalue":{"value":{"amount":"+0.8252158164978027","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1406046$118209AD-F668-43A6-ABF9-5FBEEC0EA59B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea781d2b4b1b63c6e4ca66c22f288eb84ac9821f","datavalue":{"value":{"entity-type":"item","numeric-id":1897361,"id":"Q1897361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c19cf933e0bf02dfbaece6de80fd08d3e4192ab","datavalue":{"value":{"amount":"+0.8241152167320251","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1406046$CCF18409-C3BA-45CF-94E6-6B79300703E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32ec3dfb75a83121149248751be2001ccf6af098","datavalue":{"value":{"entity-type":"item","numeric-id":1183332,"id":"Q1183332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"497dba9b57bd0b7cab2699778bb64b4b4e72a4cf","datavalue":{"value":{"amount":"+0.8234966993331909","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1406046$783F0BA7-9493-420E-9D13-3533C331371A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f2ce9cbdecf95d209987b53b83884e903dc57ba","datavalue":{"value":{"entity-type":"item","numeric-id":3990660,"id":"Q3990660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"878836992ac51b6a8f0fdae98b61c766cd99b72b","datavalue":{"value":{"amount":"+0.8196746110916138","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1406046$4A75DE1F-69AB-462A-A85C-455BF0EE5323","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1406046","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1406046"}}}}}