{"entities":{"Q6168932":{"pageid":13303818,"ns":120,"title":"Item:Q6168932","lastrevid":98870639,"modified":"2026-06-05T18:41:13Z","type":"item","id":"Q6168932","labels":{"en":{"language":"en","value":"Two generalizations of proper coloring: hardness and approximability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7724735"}},"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":"Q6168932$2CFF6043-80D5-4A98-A2C6-9F7A237CAD76","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d29d1de2978891405cfb20983976e475b041d2ed","datavalue":{"value":{"text":"Two generalizations of proper coloring: hardness and approximability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6168932$14097AE6-D04D-4D7E-B035-D0E4AD349306","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a7fbcdc895457ce5345fb3a9be9b442209da7d87","datavalue":{"value":"10.1007/978-3-031-22105-7_8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6168932$DE639121-D91F-4CFD-8098-35F3EDAA5920","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad6996603b7850d02c6839571cce935453d8b075","datavalue":{"value":{"entity-type":"item","numeric-id":1946834,"id":"Q1946834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$18E78A35-F8C5-460F-B91B-1A352E6FCE8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05437bba94b845806f30a1c8fcf0e8e57922d1ce","datavalue":{"value":{"entity-type":"item","numeric-id":1983327,"id":"Q1983327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$6DA3E290-F516-4346-9CBB-E638BD82A70B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$309454D3-D020-48E0-86BA-7FB59377B748","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9dae15c90b98a92864cf67eed8eb0b97ddf8177e","datavalue":{"value":{"time":"+2023-08-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6168932$FE83D800-4C78-4A03-8A37-4339E7FE820D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1397c7d07b55282862d4db12cbe94becf8137559","datavalue":{"value":"68Rxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6168932$359C15BC-F7F9-4C95-800F-43C61006E921","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"27a91fa31be7e52d5f24d472b186ea9689ccd760","datavalue":{"value":"7724735","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6168932$09D4DF09-12D4-4B1A-ABF6-2451894C7234","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6168932$942983D3-AFCB-47D3-B81F-7B12B749AF0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee63604621b6fd9d90b10f19ccdd9c167a66b1b6","datavalue":{"value":"parameterized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6168932$CE510021-5237-4BFF-B6E4-7767AEA556E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd00c48d13560af13a3d1074cbfb041f87deec30","datavalue":{"value":"unit disk graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6168932$19CCD292-42D8-4B69-880B-A39B48822312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q6168932$C000935B-8AAB-4172-BD0B-850894E10CAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q6168932$F03B002D-6E13-4A6A-8ACC-005245F0282F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3f05553a5308936a7205a0d3afccb9b8d271916","datavalue":{"value":"exact algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q6168932$1270FFD0-6CE1-404B-9D0B-6F9069482EA7","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":"Q6168932$B7F49318-5DAA-40E8-8A42-AC1BF225C3BA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7df57253722090f9090dc59373da49ece64d44fd","datavalue":{"value":"https://doi.org/10.1007/978-3-031-22105-7_8","type":"string"},"datatype":"url"},"type":"statement","id":"Q6168932$26E10516-4893-4CB4-AAE9-3301C493880A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e12b2838137b651b6a7ae34d0cf543958fb8778b","datavalue":{"value":"W4313351200","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6168932$5EB46E69-87E9-41D3-8578-946F60BDD66C","rank":"normal"}],"P223":[{"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":"Q6168932$6F689FC1-F543-44CC-8B87-EB20C74BD861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b129cd3c5d98bde86a845a5a7ea864b05a8a86c","datavalue":{"value":{"entity-type":"item","numeric-id":5009486,"id":"Q5009486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$118445E6-5443-4D51-8CFE-5B4162725CE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08cc9cdd9999a46859ae4f667ab34baac016718b","datavalue":{"value":{"entity-type":"item","numeric-id":5502162,"id":"Q5502162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$13943172-2493-4966-B310-47FE0CCC31C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e5cd605eb1e15481a74490dab02f39912223ff3","datavalue":{"value":{"entity-type":"item","numeric-id":2433802,"id":"Q2433802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$C110A79D-4EBF-48E8-AAF7-D718E91E81EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81078a7460abf00d8505be96a597e8d07c36cc68","datavalue":{"value":{"entity-type":"item","numeric-id":3771608,"id":"Q3771608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$15F029B0-15E9-4FF4-95AA-84FCCE5A0424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"230b49c720f6869dddbfb15df36ba80047a15815","datavalue":{"value":{"entity-type":"item","numeric-id":782177,"id":"Q782177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$0162A8BB-E047-46D7-9239-A9C453DBD38A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08679e1302d53c12ee04f803b2320a1e4c7b1a0b","datavalue":{"value":{"entity-type":"item","numeric-id":606873,"id":"Q606873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$DDE47E29-D7E4-4D7A-8262-0C53650EFDA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0be4a2d78cacd52baf04c977e2292e9d5fa6de58","datavalue":{"value":{"entity-type":"item","numeric-id":5897569,"id":"Q5897569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$D8E1D12E-8AEE-4570-9F92-12E113B64CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a60f4d593f7d2a67c047ec4f17315aa60febd9c3","datavalue":{"value":{"entity-type":"item","numeric-id":2864316,"id":"Q2864316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$899AED66-E228-42BA-ACF9-7E1A565D6422","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9524d11e3548fa2018d0863de095cec92224865","datavalue":{"value":{"entity-type":"item","numeric-id":4152030,"id":"Q4152030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$70507B7D-5EAB-4A70-B024-8ED746FD8651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67e045918d0b6345cb266826fbaa1b27a94f4bfc","datavalue":{"value":{"entity-type":"item","numeric-id":5710802,"id":"Q5710802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6168932$EADBA4EF-96D9-4D4E-A014-948B0568D8DB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d619d12577cf9de3bf4241d04b71c86fbb29220e","datavalue":{"value":{"entity-type":"item","numeric-id":5091252,"id":"Q5091252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47fd17a495889efda25195e90992eefa04b8b1db","datavalue":{"value":{"amount":"+0.894505","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6168932$1FB4D4EB-04C7-4A1A-AF9D-032759147CBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdf0faf64aa779da571c611ddc85fe20d2c12840","datavalue":{"value":{"entity-type":"item","numeric-id":1923585,"id":"Q1923585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b77e70aeb8e5c931730fc1b07daac0ebd5f54196","datavalue":{"value":{"amount":"+0.8937882","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6168932$73DFB661-F29B-4DC6-B0DA-9968DF67111A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a0380154964293e12482505fd34e4e9d84e8685","datavalue":{"value":{"entity-type":"item","numeric-id":5932643,"id":"Q5932643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a95a111e141acc1d1f74b6730e458d233553b775","datavalue":{"value":{"amount":"+0.893725","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6168932$17D0600B-800A-48AE-A0FC-69D4A397A7B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"212478c801e07e81d3dd9d5ee9b9008712198de7","datavalue":{"value":{"entity-type":"item","numeric-id":3149889,"id":"Q3149889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3de3518f1c3e974ebe81c716bb2864668a4cbc26","datavalue":{"value":{"amount":"+0.8923205","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6168932$527C133E-6DC5-4824-8805-124961E4ED05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19ca86486705309b4cd62bf7986d549fce4c5d5c","datavalue":{"value":{"entity-type":"item","numeric-id":2931398,"id":"Q2931398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e00b7a4edd104179049a653e673f4f8af04185b3","datavalue":{"value":{"amount":"+0.88850826","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6168932$868688BD-9EBB-4297-9881-014AC6E7DFAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22af9ce8516bf485396eefff569fbeb784812103","datavalue":{"value":{"entity-type":"item","numeric-id":3575151,"id":"Q3575151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e00b7a4edd104179049a653e673f4f8af04185b3","datavalue":{"value":{"amount":"+0.88850826","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6168932$BCB1A3D3-B9E2-4ED0-B697-F74CC9F8B92B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1af5fdd49cecf26e50701432e4117b085aebde86","datavalue":{"value":{"entity-type":"item","numeric-id":387816,"id":"Q387816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41d3c5c6f334203fd23edd167cf936c2509edfe4","datavalue":{"value":{"amount":"+0.88663423","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6168932$63FDB396-66ED-4D2B-9C59-984DB72B00DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69e524e56114e8a331215f538fdeb8aafd0f5d4b","datavalue":{"value":{"entity-type":"item","numeric-id":2359789,"id":"Q2359789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40dc6f191a4d3d54e1f2aab61bfe12415e8437cb","datavalue":{"value":{"amount":"+0.8861173","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6168932$4F4D963E-435E-485C-AFA9-8A0A81A8C805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eddde88435ea2b4424f5a47b7bd19e467a713033","datavalue":{"value":{"entity-type":"item","numeric-id":2827384,"id":"Q2827384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a35e4ee3406c01e1d2510aa2caf04741e9e03fc8","datavalue":{"value":{"amount":"+0.8859105","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6168932$C7678936-2AD0-4D4E-80BB-557A17B39FAC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two generalizations of proper coloring: hardness and approximability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two_generalizations_of_proper_coloring:_hardness_and_approximability"}}}}}