{"entities":{"Q2209886":{"pageid":2220629,"ns":120,"title":"Item:Q2209886","lastrevid":57779883,"modified":"2026-04-02T12:14:28Z","type":"item","id":"Q2209886","labels":{"en":{"language":"en","value":"Clustering powers of sparse graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7270343"}},"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":"Q2209886$EBCE4988-D2C4-4DDF-9EF9-2216D7E9C19F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"54e2a18a09077e14af2332c0499dcdd11ae2d576","datavalue":{"value":{"text":"Clustering powers of sparse graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2209886$A0D9FA60-56EF-4B6A-928B-6858F9471408","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"941a3c6c84a88207093d10681984356b741cc663","datavalue":{"value":"1451.05131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209886$00BF0080-89A9-4123-BBF1-D353AEE81DD8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"179c8b3efa0a5697dc266652d3639dc1d929cf09","datavalue":{"value":"10.37236/9417","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209886$F8789572-22E3-4857-8670-DF5B67C6BF66","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380c4124a5ef272e2152da1b5d415130e3e64f8","datavalue":{"value":{"entity-type":"item","numeric-id":175596,"id":"Q175596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$CECA7316-A77B-44C1-9BEA-1659C7C71753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e07e2811d8526e9d2bf7c2061a6507bd9fb3972","datavalue":{"value":{"entity-type":"item","numeric-id":175580,"id":"Q175580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$1D685BCB-7F1B-4999-B661-EABA8A352FDB","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":"Q2209886$E7816FBF-BAF9-4F2C-B284-B7FDDC1F33B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6b19b09c7519f38384d021f845694abb1cfab04","datavalue":{"value":{"entity-type":"item","numeric-id":168189,"id":"Q168189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$BE65B606-2CEC-4503-B65A-2A8030911618","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":"Q2209886$23B9AB4C-DE8D-4C38-A2DB-BE94C46D1B5D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0aa71f2549cafe88468a911374ac89171b141e84","datavalue":{"value":{"time":"+2020-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2209886$210654D3-432E-4189-915E-AD29267780AA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6eaadc4c4b1f75be3f7b625d6704fa0dad61646e","datavalue":{"value":"https://arxiv.org/abs/2003.03605","type":"string"},"datatype":"url"},"type":"statement","id":"Q2209886$9B0FB7D9-B19B-455F-9EA7-0C7574288AA1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3cd109492f616ef1307ec996085207fb2073af41","datavalue":{"value":"Summary: We prove that if \\(G\\) is a sparse graph -- it belongs to a fixed class of bounded expansion \\(\\mathcal{C}\\) -- and \\(d\\in \\mathbb{N}\\) is fixed, then the \\(d\\)th power of \\(G\\) can be partitioned into cliques so that contracting each of these clique to a single vertex again yields a sparse graph. This result has several graph-theoretic and algorithmic consequences for powers of sparse graphs, including bounds on their subchromatic number and efficient approximation algorithms for the chromatic number and the clique number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2209886$D40F949A-5F68-4B5E-B1F8-FD4D52878FE6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209886$EEDC6837-8567-4185-9A08-B5C4C080FD80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209886$8CE55FE8-4415-4BD9-8F3A-884906139CB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209886$421BCB91-0D43-4C30-AA14-6D93F96AB2AA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e5a72fb9ea3f176d18e523172937178d3dd81c0d","datavalue":{"value":"7270343","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209886$ECA36D83-E6E8-4483-BF72-0DE3270D8635","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2209886$E76C8F1B-FBA3-404E-B179-55900E319546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2209886$9C187B66-08E5-4C95-A5F2-1056265E5B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83acab072da06d5d7ebb766ce7b1a8b6b4524ba5","datavalue":{"value":"clique number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2209886$EAF44625-AA23-4420-ABB4-1DA558EF4CEA","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":"Q2209886$4D7D08F1-D266-4133-B037-3B626A6C77C2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2e4773701e015bbb63ae3b6fab1b3c08f163bc16","datavalue":{"value":"W3095903540","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209886$6CAF48ED-CDCD-41F4-963A-DA12798AD0D2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1bf11fbf05e0653bb313170b8dfb7d8e67ae26e","datavalue":{"value":{"entity-type":"item","numeric-id":1823255,"id":"Q1823255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$1F6D6F98-5DBF-41E0-8F1F-493E538E4120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0c60288eab0b51d8648e306a76bbf788cdf6667","datavalue":{"value":{"entity-type":"item","numeric-id":4330739,"id":"Q4330739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$5A26B181-3C26-400C-B34C-54E926234CF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54781c9950a8fdaf065e7dd63c5ba63d6905b090","datavalue":{"value":{"entity-type":"item","numeric-id":5090476,"id":"Q5090476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$4015721D-9CDA-4754-B7EE-B9E51A04924E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b8b0cd413cf857f8f91c865df31bc8a10cb20d8","datavalue":{"value":{"entity-type":"item","numeric-id":5121280,"id":"Q5121280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$A9E9F7E7-89D9-4DF1-91E7-FD91E02F54A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b52d38642291b912b3c66870b59b7955113fa8a","datavalue":{"value":{"entity-type":"item","numeric-id":4625695,"id":"Q4625695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$9ED38DAE-586F-4D5B-870B-1C6C139FD065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0676da0284cb2bb0fd8a79c07233f7dc3249a3b","datavalue":{"value":{"entity-type":"item","numeric-id":5920084,"id":"Q5920084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$15FC8458-9FD2-4189-A52D-40C88155EF60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74c25e4752494ba376f6774236f3dc27008b0ae4","datavalue":{"value":{"entity-type":"item","numeric-id":1826511,"id":"Q1826511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$EEBBC6D9-D2F1-41DF-BB17-BC272616999A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e798232265effc58e1a57adf6162e165fe140d7f","datavalue":{"value":{"entity-type":"item","numeric-id":5918207,"id":"Q5918207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$41599143-2E80-4733-B264-5FA9BA020644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c5f21e49ae28c7bbec74ca57fc1a6d4cfcb26e9","datavalue":{"value":{"entity-type":"item","numeric-id":5851109,"id":"Q5851109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$FF889841-5C85-4B59-B8C6-D1B2B2812E72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b566012aa7100309ae3d6ac6ec17668692cdf74d","datavalue":{"value":{"entity-type":"item","numeric-id":2493118,"id":"Q2493118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$C6D61DCD-B62F-4303-B194-B419E7245F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d639d539a34bd9f2eadace636bc10b6d7599ff3","datavalue":{"value":{"entity-type":"item","numeric-id":2426456,"id":"Q2426456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$FCEBA81C-4FBA-4EED-95E5-3AB26FE079AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6d71e8e9e23e8ccf7fd49dc162cd1febeeeb202","datavalue":{"value":{"entity-type":"item","numeric-id":2426457,"id":"Q2426457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$347BF5F9-A338-4EDB-9E46-66B3B2650E0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ea7412574ac66a8bb476d957197ef0d995a543a","datavalue":{"value":{"entity-type":"item","numeric-id":2430977,"id":"Q2430977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$FA8CB3B1-1389-4BF3-9823-9E3B4FCCB0F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1126028165ed25aec0b23ea9dd66a35457a4e03a","datavalue":{"value":{"entity-type":"item","numeric-id":419416,"id":"Q419416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$D77E011E-00CC-4481-B3E7-A62493185756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f84ecd1a0f3c9b4ffaf9caf6c01f8e4e0409b14","datavalue":{"value":{"entity-type":"item","numeric-id":1045038,"id":"Q1045038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2209886$A74B8AC7-6E71-47D2-AE2D-9FDBE33A11BC","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"d700ee48dc9e9daacaa7ff1870d154643d746f15","datavalue":{"value":"bafkreidteejarwcesp2yovgh2b32b5ai6t2vwnval2674m3feoo3h7z2ce","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2209886$3DD5FC14-9DCC-4992-97FE-8F71F29C7396","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e827e0cbd9f72cf393cadcce8ab7808cb4765c98","datavalue":{"value":{"entity-type":"item","numeric-id":3601929,"id":"Q3601929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fea42464f6019399844d1d983fb90df4c576aeb","datavalue":{"value":{"amount":"+0.7635002732276917","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":"Q2209886$2B7531CA-5798-4233-96FF-FD1AF6B81574","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"000fdcaa8e5dff5ad66790f5a279bea0ae41f699","datavalue":{"value":{"entity-type":"item","numeric-id":419416,"id":"Q419416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e1e4a360098aa98f420a4678d66eb7f5dc6cde7","datavalue":{"value":{"amount":"+0.7595715522766113","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":"Q2209886$B15C39FB-2658-4271-877D-F058D9041BA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcc425cd62c4e46577dfad877173639491f6ebf3","datavalue":{"value":{"entity-type":"item","numeric-id":5857003,"id":"Q5857003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01201869b5eac4d20c1cdc1ba89cd36e8c916132","datavalue":{"value":{"amount":"+0.7580519318580627","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":"Q2209886$22914DBB-61BA-42F9-BEE9-2E12FEAF28CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e06543cc3cc2c90a94fa12afe04dd70fc7d27e38","datavalue":{"value":{"entity-type":"item","numeric-id":3094934,"id":"Q3094934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c9a6934425024c4b602634cd4070b0cbfc16d26","datavalue":{"value":{"amount":"+0.7431206107139587","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":"Q2209886$9D00D5C3-0E81-4615-889B-ADC60AD593CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d04ec17ea06780e2706aed782aa3deefd06e84e","datavalue":{"value":{"entity-type":"item","numeric-id":896650,"id":"Q896650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00b634ed147475159e9afc5b5e33081d310dcac5","datavalue":{"value":{"amount":"+0.7415494918823242","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":"Q2209886$D7285A92-C145-457B-8F8A-B9B691B24A33","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":"Q2209886$7C8CC14F-B1ED-42F1-B6C3-817CBAAA70F3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2209886","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2209886"}}}}}