{"entities":{"Q1108293":{"pageid":1119042,"ns":120,"title":"Item:Q1108293","lastrevid":69661437,"modified":"2026-04-13T08:32:22Z","type":"item","id":"Q1108293","labels":{"en":{"language":"en","value":"Paw-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4066954"}},"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":"Q1108293$92E2E2B5-1C44-4F1D-BB0B-E80153267D2B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ebbe21a10bba5bf2721964a245cb559a0422ee75","datavalue":{"value":{"text":"Paw-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108293$E5175563-F062-48D6-8615-26EC05A9524D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"87a29838c61888fba320804db4e7224253e594a9","datavalue":{"value":"0654.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108293$BDF32CEA-B30D-45A1-B882-60F171A52B37","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e2f7c56b811818bff5f50f9f72b9f1e70d84073e","datavalue":{"value":"10.1016/0020-0190(88)90143-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108293$F666082D-C7C9-4DFD-99C5-6D335D46442B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e7020a54266d4b2ab3b7f83a2814036c1ab56ec","datavalue":{"value":{"entity-type":"item","numeric-id":185063,"id":"Q185063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108293$22E29D8D-76A4-4ABC-A1F9-137466ECC418","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108293$19132A7F-6F1C-47E7-8952-EDF95091F729","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1108293$6A27B472-81FA-4BB6-BF37-736AE2F9304B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"36a1ccb9ba9cd55bdd5c364a0e6e8aae67a50706","datavalue":{"value":"The graph with vertices \\(a, b, c, d\\) and edges \\(ab, bc, bd, cd\\) will be referred to as the paw. A graph \\(G\\) is called paw-free if it contains no induced subgraph isomorphic to the paw. We characterize paw-free graphs and give polynomial-time algorithms for recognizing them as well as algorithms for finding the largest clique and the largest stable set in a paw-free graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108293$09276C59-B8C6-4A99-98D3-4259DF22E35A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108293$5B489005-F617-4F2E-9804-EF5403AF940A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108293$25BBB168-74FB-4D46-B1AF-D03F9BE4E582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108293$A0344D93-B9EA-4DB4-BFFE-608996E5C875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108293$A75B2ACC-BDE5-4599-90F8-9BEF6DE5C183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108293$4DEBD127-B6AF-48EC-8286-0CA7B3BEA649","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d06a6f9b8e171914f10310bd83da37c2bc0ac37","datavalue":{"value":"4066954","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108293$AC435831-D02E-4F3E-9C42-1EF182A76A6D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cee46e2c6a42a74803d50f6329947494bb4a53f6","datavalue":{"value":"graph decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108293$8EAC6F6C-1878-4D1E-9DA1-CD9A8ECC3458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108293$2CDD2E41-7775-4A77-A496-85CF4D720CDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"459b1112f3c9208864d21e9010c65284a0957db7","datavalue":{"value":"decomposition theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108293$AC03490E-6336-4138-A68B-6E445B520040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108293$A0E58B73-6FCB-4A2F-AE0C-7FEAF2009122","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":"Q1108293$F7CD7FFC-8286-4D0D-815C-2F821B93D305","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c3d1fb1053d9f721fc32340dac9331b452b031e9","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90143-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108293$233CF720-B316-4C6E-AF4B-0057DB4AB35C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6176298b203b412250b46b3e792f35b15ed606f4","datavalue":{"value":"W94262720","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108293$CF302AA5-C6C6-49C5-8DB5-DFB634E136DA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8a74f042ba1f29a12a670ab9d659cf777707121","datavalue":{"value":{"entity-type":"item","numeric-id":798301,"id":"Q798301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108293$FBE170A6-DD3D-4A4A-ABB6-E0704889EE66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2d67bd3980ca4eba682fae6d5244771f4d9299e","datavalue":{"value":{"entity-type":"item","numeric-id":3222875,"id":"Q3222875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108293$8C7F36CC-4B77-43C2-AEAC-44181A05E6C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8439cd84a49b5225dfa76205f17bb5321104a88b","datavalue":{"value":{"entity-type":"item","numeric-id":3222886,"id":"Q3222886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108293$DBEA4178-F0DD-4BAB-ABB3-EA252AE66905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9bd269295ba877c106cd58908caf0f087a4411b","datavalue":{"value":{"entity-type":"item","numeric-id":3347930,"id":"Q3347930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108293$866CDD90-75F2-4EEE-9E9E-F79442B2C95B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4af1dfbef55e5c6f877defc758d39f47fcfc762b","datavalue":{"value":{"entity-type":"item","numeric-id":1118619,"id":"Q1118619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108293$520DFB18-EF98-4F4A-8AED-96E3DFCBAF80","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":"Q1108293$6F041D86-3644-4B8E-9D0D-402E8B0A8917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b98563bc8bc8d33f1ddc02852b7b5f4d9529435","datavalue":{"value":{"entity-type":"item","numeric-id":1175981,"id":"Q1175981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108293$1DDD77C9-8B3D-4434-BBD2-749619BF45B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f14929504188a53ef660023bd30753f8781f60c","datavalue":{"value":{"entity-type":"item","numeric-id":1104342,"id":"Q1104342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108293$C1536B1A-5ABB-4B32-8B3E-430F2DE6EC30","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"512c0c4b5cf39695ebd288cba94bd7d15a0249c7","datavalue":{"value":{"entity-type":"item","numeric-id":1810626,"id":"Q1810626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8e5b8176c9021eeaded9af80aaca46962db0ee8","datavalue":{"value":{"amount":"+0.8142693042755127","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":"Q1108293$66F2DDE1-0665-4CBF-BF63-9A3342B8DBF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8dacbe37839bd0890cfd12f2957b17067cefc9c1","datavalue":{"value":{"entity-type":"item","numeric-id":947722,"id":"Q947722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d89bfa6d3543565d4094207c20dc9633f579ef5d","datavalue":{"value":{"amount":"+0.7866895198822021","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":"Q1108293$682A7686-58F4-4D9F-A5A7-71CBB1228A90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f5be330b21b29ed0815bc6420626d9238c2cb7b","datavalue":{"value":{"entity-type":"item","numeric-id":1118619,"id":"Q1118619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05de9b4145d2dc2f78a4d102a7ae84dbbb1d2969","datavalue":{"value":{"amount":"+0.7851511240005493","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":"Q1108293$575E4FFE-B236-447E-9FC1-E715BEADBDB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ba00655b04ffe19d6bc17448f4986819c2a74d4","datavalue":{"value":{"entity-type":"item","numeric-id":958695,"id":"Q958695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"adcfb4c08d00287044e2115b810579bf550dfc34","datavalue":{"value":{"amount":"+0.7653723955154419","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":"Q1108293$2CC5DEA6-21C7-4057-BCC7-7A30BE969086","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37d3c1e987bbb3180327f36a777d076cd318d026","datavalue":{"value":{"entity-type":"item","numeric-id":3416248,"id":"Q3416248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22792db2d6addaeb9b75946ca9784415a9c07707","datavalue":{"value":{"amount":"+0.7630429863929749","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":"Q1108293$668AF463-67D5-4755-AD8B-8661D48F93A4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Paw-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Paw-free_graphs"}}}}}