{"entities":{"Q2227825":{"pageid":2238568,"ns":120,"title":"Item:Q2227825","lastrevid":57803103,"modified":"2026-04-02T14:37:04Z","type":"item","id":"Q2227825","labels":{"en":{"language":"en","value":"Covering minimal separators and potential maximal cliques in \\(P_t\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7310930"}},"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":"Q2227825$E57B85F7-331C-4EBF-9345-4486BFD76C9A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"11645edb2aa01bbd5d8251a6b87cb55124e405d7","datavalue":{"value":{"text":"Covering minimal separators and potential maximal cliques in \\(P_t\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2227825$044154C0-2C72-4120-B9E5-285A4F44F57C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5f470c264b3eaa4df384bc40a1a53004af00d824","datavalue":{"value":"1458.05194","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2227825$45980C51-D6A8-486D-BAE9-14CAE01BAAEA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0145c4e082612fd9279818756789177c94747d3d","datavalue":{"value":"10.37236/9473","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2227825$861619B6-7B67-4375-9142-184ED9C4D097","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"814777841608649a46c3af1c5707b34163ccd36e","datavalue":{"value":{"entity-type":"item","numeric-id":473102,"id":"Q473102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$87C87E8A-4C27-4D5C-BFCB-3ED22B2E4D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"42d34822cfc8beebd2b4581d3c14e02d3080eff8","datavalue":{"value":{"entity-type":"item","numeric-id":338580,"id":"Q338580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$36C94C01-D703-4B37-9887-A3425A381E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8393ad112fe8548ea40a3793cd450c8b7586360e","datavalue":{"value":{"entity-type":"item","numeric-id":255284,"id":"Q255284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$6C9FD1BB-A481-486C-A6BF-D445D963231F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e229a7272481236f52fa95a4480b3f630728e07a","datavalue":{"value":{"entity-type":"item","numeric-id":262250,"id":"Q262250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$6687FE20-94CE-422D-9D8A-9C7F5EF665DF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$A8022DF6-09F9-4F5D-B73B-EFC0797D3EBA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ffb6d0c59335c1f7f7c958651ce65d4dd55c412f","datavalue":{"value":{"time":"+2021-02-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2227825$40826ED5-9C97-426C-AFC0-DE13EB64409C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1b03ee4a7907ec7453c4fb74d7e09f17fb889803","datavalue":{"value":"https://arxiv.org/abs/2003.12345","type":"string"},"datatype":"url"},"type":"statement","id":"Q2227825$4EC3A6EF-30EF-421E-B1CD-8C0365C57413","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a2a6e2c776c0fe45ea8c97ec47ce50a865c27e15","datavalue":{"value":"Summary: A graph is called \\(P_t\\)-free if it does not contain a \\(t\\)-vertex path as an induced subgraph. While \\(P_4\\)-free graphs are exactly cographs, the structure of \\(P_t\\)-free graphs for \\(t \\geqslant 5\\) remains little understood. On one hand, classic computational problems such as Maximum Weight Independent Set (MWIS) and \\(3\\)-Coloring are not known to be NP-hard on \\(P_t\\)-free graphs for any fixed \\(t\\). On the other hand, despite significant effort, polynomial-time algorithms for MWIS in \\(P_6\\)-free graphs [\\textit{M. Chudnovsky} et al., in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6--9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1239--1256 (2019; Zbl 1431.05064)] and \\(3\\)-Coloring in \\(P_7\\)-free graphs [\\textit{F. Bonomo} et al., Combinatorica 38, No. 4, 779--801 (2018; Zbl 1413.05101)] have been found only recently. In both cases, the algorithms rely on deep structural insights into the considered graph classes.  One of the main tools in the algorithms for MWIS in \\(P_5\\)-free graphs [\\textit{D. Lokshantov} et al., in: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5--7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 570--581 (2014; Zbl 1422.68126)] and in \\(P_6\\)-free graphs [Chudnovsky et al., loc. cit.] is the so-called Separator Covering Lemma that asserts that every minimal separator in the graph can be covered by the union of neighborhoods of a constant number of vertices. In this note we show that such a statement generalizes to \\(P_7\\)-free graphs and is false in \\(P_8\\)-free graphs. We also discuss analogues of such a statement for covering potential maximal cliques with unions of neighborhoods.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2227825$EFBC338B-AD54-4012-985E-913FE49CC8C8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2227825$B037F6FB-972D-4D48-A781-86B10E71E84F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2227825$636282A5-ADE4-4AA5-A527-862BF1A1F072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2227825$266ABF61-CA43-4D23-9E1B-2D4FB38CFAD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2227825$A889BEEA-EF78-4907-BD6E-904B4842650D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2227825$74A27D3C-0197-42AF-8185-15818A2D3796","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f90fe23a375b86101707e7f71076fc96fbe1be6a","datavalue":{"value":"7310930","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2227825$AB48045C-63B5-470F-96F6-6C75BF026AEA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d50dba714528f7e5f5796bd945019cd62285cf2d","datavalue":{"value":"maximum weight independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2227825$6B41E528-5426-4CF2-AE02-BB91FEC74241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2efa8cfd018309202cb6527111ab0c58b0b25f52","datavalue":{"value":"separator covering lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q2227825$C2187FB0-408E-4880-9A2A-444D2833B776","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":"Q2227825$A69224EF-E7B2-491F-9723-E044027BC631","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"16027543fea2ea6abc5df6e40b194c683817741e","datavalue":{"value":"W3129306252","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2227825$955A1915-105F-4E2B-A153-1B4AAD0167A4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecfcb71aac592bb4482582547044b259a772c946","datavalue":{"value":{"entity-type":"item","numeric-id":1725633,"id":"Q1725633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$6BE5DDCC-E706-47A8-A9D4-C05DA7BA6F3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6a0d346506465223f8a96355556be48c1ad0dfb","datavalue":{"value":{"entity-type":"item","numeric-id":1786047,"id":"Q1786047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$22C54E37-8630-4AED-BB64-C93EAAC679B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c43a5f014a72e88b824f21616de5fa914724e1cc","datavalue":{"value":{"entity-type":"item","numeric-id":2784449,"id":"Q2784449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$CCCD7ED1-059A-4589-A661-CAAD4D47487C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fe19650c5a5ca5aed27b7e62d932794418db880","datavalue":{"value":{"entity-type":"item","numeric-id":1605302,"id":"Q1605302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$0A2E5385-E5EA-4E5D-BB2E-6D89E0CA2942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"011868466312956a5fbcaede1ac6a90add6e8d3e","datavalue":{"value":{"entity-type":"item","numeric-id":2403797,"id":"Q2403797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$F24C1B19-7348-486E-B96A-9DB1151E8A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3138954d0767087e328a5039339d3578fd5e3c0","datavalue":{"value":{"entity-type":"item","numeric-id":5146928,"id":"Q5146928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$3E75D55E-7FF3-4C95-B644-FD27F77AD1C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35a44e11169a034de138802141ee5d73ec6d3d5a","datavalue":{"value":{"entity-type":"item","numeric-id":5236260,"id":"Q5236260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$950D5465-07D1-4062-BFB8-AAB204117917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de152ffe598cd9d06d05f330708cf3c4293f85e5","datavalue":{"value":{"entity-type":"item","numeric-id":2954371,"id":"Q2954371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$2820820C-3E0D-4C92-BF61-7F63EEEC61C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f08688ad89d97f94566d0f2d68d02ddad138796c","datavalue":{"value":{"entity-type":"item","numeric-id":2252529,"id":"Q2252529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$FD0D669F-3465-45F5-AF00-27628F82F290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08512096d9451fec427d4cbe7d8da8eb09fecbd2","datavalue":{"value":{"entity-type":"item","numeric-id":2322884,"id":"Q2322884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$6C9DE52C-9F99-4574-AC77-EB35C46AF60E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd2a411b16fc2c459d186cca895548cbb291c1a4","datavalue":{"value":{"entity-type":"item","numeric-id":5236261,"id":"Q5236261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$11F2E5D8-9DB0-4A1C-8CF0-CB274B350BF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93ad84d0a1a74f90cb7eae653f4eece82f4d2372","datavalue":{"value":{"entity-type":"item","numeric-id":458504,"id":"Q458504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$6C24347E-F8ED-4C39-97B0-55274416BB5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"977cd433ecde040f39e4c4dde1c0b893e5757f3f","datavalue":{"value":{"entity-type":"item","numeric-id":848637,"id":"Q848637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$7515E5F5-E34E-4905-AB1D-572F80EFC7D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7401c70f4de583980fdfd86857007d381503749f","datavalue":{"value":{"entity-type":"item","numeric-id":4554948,"id":"Q4554948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$29B33B23-BE1C-45C5-BA9A-4C41E27E23D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8807a77b16516cbd9e09421a89f1b5dfabfc8c7f","datavalue":{"value":{"entity-type":"item","numeric-id":5384003,"id":"Q5384003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$39DD8FCF-7FA4-4FE9-9EAB-5C021F11FBA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f2d5c8a3269cfb2e61de4050da1cb51a300b6eb","datavalue":{"value":{"entity-type":"item","numeric-id":5901434,"id":"Q5901434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$1F0B218D-5679-41F9-AD89-F001A93FF1B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ada71f343b2168554ef3d8e68058bb18dbed1fd2","datavalue":{"value":{"entity-type":"item","numeric-id":1139605,"id":"Q1139605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$AF146DAE-A901-49A6-8F28-D048DDC164C9","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c8df1584806a49b511d4ccc7ae061974abf87e56","datavalue":{"value":"bafkreibhqzt6xqckpsrkc56pcz4npvksodjlhmnd3f64ed6dcadkvgzo6m","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2227825$0B1EC708-EBC8-41A4-9852-FAD1ED3C5F9B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c13e1e2fdc78dcc339abbb26369bad098415ea91","datavalue":{"value":{"entity-type":"item","numeric-id":5110670,"id":"Q5110670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dda5499bc9f2263e3891cd07fc76c170444cc80","datavalue":{"value":{"amount":"+0.7832230925559998","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":"Q2227825$9D84FB8D-FF0A-4724-A774-92577BC387E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c59f2f669b65833bf5a4f8f3ca180543e3b0aa9f","datavalue":{"value":{"entity-type":"item","numeric-id":499486,"id":"Q499486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a69eb2c4083baa1ffd9c35a8ce5f92066018eba","datavalue":{"value":{"amount":"+0.7763229012489319","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":"Q2227825$A691CE17-735B-41E6-9F73-8E1A901A9605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1fc35f1744ceaf4dd042e1684ed7a139e6be218","datavalue":{"value":{"entity-type":"item","numeric-id":2664556,"id":"Q2664556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4172aaea94464c157fcad2607857d0eed6676810","datavalue":{"value":{"amount":"+0.7669654488563538","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":"Q2227825$8DCEF9F6-6AF0-4777-90D7-87A837EB1559","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef4a5b069131ab4703bc08f14b0d64a80d6c079b","datavalue":{"value":{"entity-type":"item","numeric-id":2849942,"id":"Q2849942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cbf456507881fd96d70c041affd0e2f979e917a","datavalue":{"value":{"amount":"+0.7647563815116882","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":"Q2227825$9A873989-405D-4E22-9F2A-9C861E79CE03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c057ae6b12887c2aef5d0a2f3e62eb8dff627d98","datavalue":{"value":{"entity-type":"item","numeric-id":4915195,"id":"Q4915195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2534634729145e8353a8f09dcc3a4bbecf55d2f","datavalue":{"value":{"amount":"+0.7614219188690186","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":"Q2227825$45BA8471-11D5-4B30-BA79-449BEC13F82F","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2227825$950B808F-300A-42BA-946D-47107A92AB1F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2227825","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2227825"}}}}}