{"entities":{"Q5075768":{"pageid":7105344,"ns":120,"title":"Item:Q5075768","lastrevid":91333175,"modified":"2026-06-04T22:54:13Z","type":"item","id":"Q5075768","labels":{"en":{"language":"en","value":"Complexity of \\(C_K\\)-coloring in hereditary classes of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7525468"}},"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":"Q5075768$AC8AF173-2AF3-4524-848D-6E8D9599092F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86791d2de8f741697c1a28c841b5e520b1ea6f17","datavalue":{"value":{"entity-type":"item","numeric-id":256974,"id":"Q256974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$691AF31E-050F-400F-9303-56AE4697390B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ffcb0dd2a6744d126324d646018940643ff5d16","datavalue":{"value":{"entity-type":"item","numeric-id":322307,"id":"Q322307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$5F3B2FB8-5FCB-436C-84B4-A6C8ACF4A9F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2f04fa19c2b8e8035a111d77d70f9134fd5fde43","datavalue":{"value":{"entity-type":"item","numeric-id":322248,"id":"Q322248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$F8EA5C24-2A56-48AC-B262-B4B2080774A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f84c2585906a3dfec8dc78c048cfc8b3b8be2285","datavalue":{"value":{"entity-type":"item","numeric-id":345122,"id":"Q345122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$8D3D5948-A3B5-4FC0-89B9-5FE61C6BF479","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"502fa3818c0729e7c2c4e3414e0aefd1ba7e2488","datavalue":{"value":{"entity-type":"item","numeric-id":1637132,"id":"Q1637132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$49F159E1-3CB5-41B4-B35A-391D8FCD16B6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"33eb095e7a11594535a14f244480079f6a32a297","datavalue":{"value":{"time":"+2022-05-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5075768$85D119B0-E2CE-4FC8-8742-FA7BD8DD6CB1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cdd1a619ca2fc9b48c7d8b7a2e9e0185533b2e32","datavalue":{"value":"https://arxiv.org/abs/2005.01824","type":"string"},"datatype":"url"},"type":"statement","id":"Q5075768$C328E8E0-B8A9-4417-8BB3-42191608A97C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa684c8d52e9da1094b0c2d762898ace723c7ee3","datavalue":{"value":"68Wxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5075768$0729AAFD-3731-4B9F-A81A-6B01E70C066C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dbfc6ccc0c91d1c3d484d75fcf361f9e26d14a41","datavalue":{"value":"7525468","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5075768$2DC52612-7C9B-4611-A5E7-718FDBBB7D7C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q5075768$B695B5A4-585F-4554-B67E-53EC8BC07000","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"055f7bdcda7b7c8eaba57b32556f5997168338c8","datavalue":{"value":"hereditary class","type":"string"},"datatype":"string"},"type":"statement","id":"Q5075768$CC1B75DE-7A99-4937-8EA7-890915C92B5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5075768$B1CBBEA9-EC5A-403A-928F-C80B5D16D042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6fac036d0386461048e4af513ab5529434c4260","datavalue":{"value":"forbidden induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5075768$0304CC41-B5DE-4956-A566-EFAD1B5C2712","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":"Q5075768$BFCDA50B-F526-4653-BCE3-F00AA20E85D6","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":"Q5075768$BD694A23-E353-47F7-B86A-16101C33ABD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f92a64324b680cc8236beb143a28fcd1f34aade6","datavalue":{"value":{"entity-type":"item","numeric-id":444433,"id":"Q444433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$002EA6C1-9EB7-41E2-B2DD-908007D75DDE","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":"Q5075768$931F8C8D-D7BC-44FA-BE20-03FD7B1148D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00736cd525e3eb868e4710dd6110dbdbea0bfb25","datavalue":{"value":{"entity-type":"item","numeric-id":300476,"id":"Q300476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$4A602162-79CD-4AF2-9C0B-F27F7EF6018B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc56f60ab92aaea5434fb1c9885a820aa4bd6e87","datavalue":{"value":{"entity-type":"item","numeric-id":1637133,"id":"Q1637133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$7F5DC1B4-EDBF-4839-B416-BC6115B636D0","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":"Q5075768$8A18ABF2-F168-4FC3-A8E7-C46C282D8341","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d4bd16b8f988e4232f1989a0f22132674569ade","datavalue":{"value":{"entity-type":"item","numeric-id":1079363,"id":"Q1079363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$296DBA67-9643-476F-9E3E-A00D3C0F01CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53870c846ef5debcb00b9163ba6139c68150bfa2","datavalue":{"value":{"entity-type":"item","numeric-id":5246080,"id":"Q5246080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$48540E2D-49F4-49A5-A5CD-3E62767FE023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75d4076d4897ab3cc8f6948af493950051b74467","datavalue":{"value":{"entity-type":"item","numeric-id":1127870,"id":"Q1127870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$F3F0F655-CEB7-4D51-84C7-F3F96CF7896D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72636d83503e896e571d6f2c09be11cb7bc2ca51","datavalue":{"value":{"entity-type":"item","numeric-id":1977431,"id":"Q1977431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$2760F8EB-9AC4-413A-9DB2-34E5851AEAF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ff3c7043c6a33e597d303158f0c3e15848da011","datavalue":{"value":{"entity-type":"item","numeric-id":817772,"id":"Q817772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$CA1B854E-AC73-452A-B86A-52E9ECF43B8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7aaa9bb137fa2b1d06177861fbdb923853dbb86","datavalue":{"value":{"entity-type":"item","numeric-id":5248532,"id":"Q5248532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$3A455E17-A494-4E78-B4D8-917DB47147A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05f117dbc398c4ca9edf7bfdc3c9b0cc411a9c5d","datavalue":{"value":{"entity-type":"item","numeric-id":1579552,"id":"Q1579552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$85213DD7-EF8F-42BC-8D87-D84EB3DB96AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e156e31cf1c03a94ee42319c5e653b95dcd615cf","datavalue":{"value":{"entity-type":"item","numeric-id":2978179,"id":"Q2978179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$A74A2766-B019-44CF-937F-E83FE63BC9A7","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":"Q5075768$D7848DD8-37E0-4B58-8E7D-BDA2D29602CE","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":"Q5075768$96E663C1-A59A-440C-84CA-D1EC0A63566D","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":"Q5075768$99C045A0-B759-4383-B9F8-F0C2A25D5FB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a633e84f28e974524d6f21199618016457237af","datavalue":{"value":{"entity-type":"item","numeric-id":4828516,"id":"Q4828516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$F9B4C363-1888-4814-A06F-8B41D536B5BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec165abc7ade014841f417bcba31a647c17e0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$D3D17C7D-BDBC-4577-8758-C210ADF03640","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":"Q5075768$B5969579-646B-429F-9D51-40993E0BD5FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$DD3BC447-0602-4879-A7A8-E8871F7CF57F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47707362ea38a9307252d6fd07d68a2560b06ac8","datavalue":{"value":{"entity-type":"item","numeric-id":499486,"id":"Q499486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$42B32D67-93DE-4816-B3F8-9B15113797C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"112fa1e16c28072d1b690d88a68f10e9a878f19f","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$B6904AE5-09E7-44A5-B554-EAE1C31C532E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4548ea5d583917c0fa9b6aaa6b1d48c80c1e7e","datavalue":{"value":{"entity-type":"item","numeric-id":1604206,"id":"Q1604206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$CBDC8986-0C0F-476A-9741-9C045B8C87C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"920815abd7f8c7e0d9144731327c013953758a9e","datavalue":{"value":{"entity-type":"item","numeric-id":4838453,"id":"Q4838453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$5F72218C-795B-42DE-9BE3-A9529501CBBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"103b869fabbeeac0c123811b5ee7dc0266ddd85e","datavalue":{"value":{"entity-type":"item","numeric-id":393914,"id":"Q393914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$8B38E0ED-2E8E-4E3E-B597-67908B9C73FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c89b292130156cda494465abc433e8f94f18e584","datavalue":{"value":{"entity-type":"item","numeric-id":3558598,"id":"Q3558598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$B30B6DEA-C185-4594-8684-476FF98CB8FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be2a01198b1b63afd375056c2a1eff2d080abd2d","datavalue":{"value":{"entity-type":"item","numeric-id":2770587,"id":"Q2770587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075768$85E758E6-9049-4472-A1A2-C00F61AC114A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2dfdb187f9807b6acdb31d1f66daa55981082386","datavalue":{"value":"10.4230/LIPICS.ESA.2019.31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5075768$9D86C1F1-3A93-4F4B-8360-A9F1CD00962E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfc426b6223b973ddd535793633586b02acda511","datavalue":{"value":{"entity-type":"item","numeric-id":6040658,"id":"Q6040658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"805610bfebd9bf3f82bae521c3854de3aa66714a","datavalue":{"value":{"amount":"+0.974977731704712","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":"Q5075768$14310ECA-CB19-45DE-AE93-FA3FEB6DBFD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"441e219b2eb150d707cfb55e453083e80070d90b","datavalue":{"value":{"entity-type":"item","numeric-id":3651537,"id":"Q3651537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a7ed301b6b092c99373aea73fc55a0d5c2c6bd4","datavalue":{"value":{"amount":"+0.844692051410675","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":"Q5075768$8D1354D6-1FE3-480E-BD00-1816DAD34949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f1f8df513a6f43daf522bc1b5283b766d0ad73c","datavalue":{"value":{"entity-type":"item","numeric-id":1933643,"id":"Q1933643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9fcbd34a1a5ce5c63f3d80d42eb7dba5102e407","datavalue":{"value":{"amount":"+0.8443472385406494","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":"Q5075768$1E936585-E72D-4236-9FB3-3A40B6FB8F0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09b1fe45b411d07b425b1f0a42aaf4e9c4cffe43","datavalue":{"value":{"entity-type":"item","numeric-id":3057613,"id":"Q3057613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3324936079c8933b0d05f52469a5e0bae8b44c9","datavalue":{"value":{"amount":"+0.8326177000999451","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":"Q5075768$3C4CA0DC-72A7-4267-9982-44C4B23E3F03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"725706a45e47d34132f08d3ee5b699c84649d5a3","datavalue":{"value":{"entity-type":"item","numeric-id":5918691,"id":"Q5918691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52719e5c6ae5201987e28cd2ec67d1e55fa30167","datavalue":{"value":{"amount":"+0.8296152949333191","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":"Q5075768$71AA8DAF-672E-474D-AD08-A780A3587393","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of \\(C K\\)-coloring in hereditary classes of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_%5C(C_K%5C)-coloring_in_hereditary_classes_of_graphs"}}}}}