{"entities":{"Q817778":{"pageid":819626,"ns":120,"title":"Item:Q817778","lastrevid":42710329,"modified":"2025-07-08T17:50:44Z","type":"item","id":"Q817778","labels":{"en":{"language":"en","value":"Group coloring is \\(\\Pi_2^{\\text{P}}\\)-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5013298"}},"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":"Q817778$477D2121-7ECC-4629-9F2C-AADFD31C9A24","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ab148b12c974ee2e0d00a5aa9ce4b56ab10206a4","datavalue":{"value":{"text":"Group coloring is \\(\\Pi_2^{\\text{P}}\\)-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q817778$670E3BC7-39A5-4D05-BAF0-AF157BA23B8A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9a1669a47155d802354d79107cf71098ecdf1f76","datavalue":{"value":"1087.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q817778$35371FD3-48C2-4A44-8508-7A4DBC8AC2E3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"53427ddbb10f2ef6b2b23d5d0945110660ad7953","datavalue":{"value":{"entity-type":"item","numeric-id":273100,"id":"Q273100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$4162A697-E442-41AB-BD2A-7632676FA281","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$27FBD7B9-12BF-4E51-ACA1-D98B4E238418","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"87871fabe918b62ae0b497aecc54a3998d2fdfae","datavalue":{"value":{"time":"+2006-03-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q817778$80528214-8C1A-4933-BB32-4A4454E079B5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q817778$7E6CD5CA-84F5-4668-BDBF-E227E351B832","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q817778$F69691F9-6027-4EB6-81BA-35CF20889093","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2590fe5afc24433b57b280b289996f3815d8f0fb","datavalue":{"value":"5013298","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q817778$FD59CF0C-C5C8-428C-976F-4DF8244A109B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"085f0895b4d56020acb70c9696826ddcf97a985e","datavalue":{"value":"group connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q817778$A779030B-150C-458F-BD5B-8A95B8373645","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42a13380c4155a50e13969d80111097f5bb2abcb","datavalue":{"value":"nowhere-zero flows","type":"string"},"datatype":"string"},"type":"statement","id":"Q817778$E5E0FADC-A3D7-4E57-B91E-9BFE060C0E6C","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":"Q817778$685FCD4A-5F1B-49F5-9910-B0D3A1CD3D25","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c2b1e9a8ef302b2b92dc72c36c9ce3b82c4bd474","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2005.09.033","type":"string"},"datatype":"url"},"type":"statement","id":"Q817778$D3779C59-660A-4A0B-8A68-24B7D3CE2DBB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"934ec0e72e43d7b9676cea3127d53493690855b9","datavalue":{"value":"W1995928453","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q817778$510BD551-19E4-495B-B452-4CE05CCA02D3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8f7ba9b8d774790a8f9fd25936ddee3d29d1a2df","datavalue":{"value":"Q57601558","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q817778$CD435E8C-3D7E-4C96-8D9B-EF3FA09CBF28","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdd0676f008d3d35603ace258b7c421e863d9a84","datavalue":{"value":{"entity-type":"item","numeric-id":1196681,"id":"Q1196681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$7BEFBAAC-BDF8-41D1-907A-7B6FBBAA1652","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7086dea06f90ad187cd6ca8db29e29ebe9068d0","datavalue":{"value":{"entity-type":"item","numeric-id":4942157,"id":"Q4942157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$407AF3F1-F358-4FFF-B0CD-5DC95694D4CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3573b87026595a32002fa2dc54ac8b096bc29f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3922703,"id":"Q3922703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$6704C532-E24F-459F-B499-3CF04248D2B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91504ac4814e7d3d74ed456613277e386680dfc1","datavalue":{"value":{"entity-type":"item","numeric-id":1204467,"id":"Q1204467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$C066BED7-E960-44D0-834E-018C583E20A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c574106149b124719a1cce56f5b240da49a47a01","datavalue":{"value":{"entity-type":"item","numeric-id":5706477,"id":"Q5706477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$6E88FA87-38BD-4264-8C3C-21ECDF0CCF80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"583bc40b6bfa6176b286fe2f26bac9412b0ed7b2","datavalue":{"value":{"entity-type":"item","numeric-id":5461502,"id":"Q5461502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$B507E1D4-6D29-4FEF-B962-6F96B1B6FCAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95a24bfcb42e3f8207e332b9520d39aeeb020b15","datavalue":{"value":{"entity-type":"item","numeric-id":1348659,"id":"Q1348659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$76BBFFCC-DF9E-4797-A7CA-E5239831800E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14499ac11fd8ed96170d36d1d408c70c4726da1b","datavalue":{"value":{"entity-type":"item","numeric-id":1305526,"id":"Q1305526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$CDC12A62-E215-4DA1-AA56-A7B310EF6B6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458ab467d1c5397109a383d0e5c939369d06a212","datavalue":{"value":{"entity-type":"item","numeric-id":3221403,"id":"Q3221403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$57F44BD6-8A02-4DCA-9151-FD3F03005218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8e9a01d057f2ac8669e7cac2ad5d67b6775d2fa","datavalue":{"value":{"entity-type":"item","numeric-id":1333334,"id":"Q1333334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$0B864C7B-7E9C-4133-95D7-C0FDFB233540","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bec1ea839bbae95cce4f38ddbbba08521d102f9","datavalue":{"value":{"entity-type":"item","numeric-id":1892853,"id":"Q1892853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$FB7350B2-8FEF-4F24-94BF-8654E29EE5A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e174f0c347a0597f5b501f1e5dded00cab08919e","datavalue":{"value":{"entity-type":"item","numeric-id":4332881,"id":"Q4332881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q817778$86E7EF68-88AB-47A3-AEF5-C68AE4449206","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"a7fa0303fe92bc24723a7aeec9b2219c3e0d54cc","datavalue":{"value":"journals/tcs/Kral05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q817778$B3819F3F-E7B7-48E2-A420-A01985900D7B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a9947b502644824dec222b688591642fe14ce927","datavalue":{"value":"10.1016/J.TCS.2005.09.033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q817778$9B91CA6E-15AE-4901-921D-A448F080AE35","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8092513fc1a82248ca44425294d7b3f341f9a87","datavalue":{"value":{"entity-type":"item","numeric-id":5311103,"id":"Q5311103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"049e138a4181e19629b66b8031b3ae26888ab6d6","datavalue":{"value":{"amount":"+0.9479962","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q817778$17ECE69A-9523-4305-A86D-65E782F660F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47060d4163a7f0c7090bfacea501424f9ffd16f2","datavalue":{"value":{"entity-type":"item","numeric-id":3063613,"id":"Q3063613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"634d5b5274449157319907e87344a62067828e7c","datavalue":{"value":{"amount":"+0.87761235","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q817778$6D23B572-A11C-4384-896E-3B2CCC075402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b25fed3e6b3a154954669814593d9dae45ed81d","datavalue":{"value":{"entity-type":"item","numeric-id":3824332,"id":"Q3824332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"521869fcae906008974bf43b29941c236c2815a9","datavalue":{"value":{"amount":"+0.8767918","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q817778$C7956970-8EC4-4308-8654-0F8B96553EFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1502cd6863ac8ac1e5c715db7af85ed6badf4270","datavalue":{"value":{"entity-type":"item","numeric-id":5706477,"id":"Q5706477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b24361d0f5e2b75047e4d14604764d697bc680f","datavalue":{"value":{"amount":"+0.8734875","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q817778$FF7C9114-F2FE-407D-8A30-47AC70964E40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fc98f27f77a978afbd1d4f94852588559266b81","datavalue":{"value":{"entity-type":"item","numeric-id":1759814,"id":"Q1759814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a226e4785459c1c4c71c7d0e9ecb581e918a227","datavalue":{"value":{"amount":"+0.8685341","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q817778$A4D410B7-E449-419D-9444-178A08C0BDDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc5d185ab2c9d4589c5038218c80bee1d03ac2d8","datavalue":{"value":{"entity-type":"item","numeric-id":5163516,"id":"Q5163516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bf8701998b4fc51b1306a8a7f450b8397b89320","datavalue":{"value":{"amount":"+0.8648041","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q817778$CBC4D074-49E4-44FF-BCAC-6765839BD93A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6871d24b771c441a36cd9fd704cffd78df3fb92b","datavalue":{"value":{"entity-type":"item","numeric-id":3110139,"id":"Q3110139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d35fc95a25e3b079e3340d89201ba9ce737bfd61","datavalue":{"value":{"amount":"+0.8647707","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q817778$E9562A24-A9D4-4247-88C1-AA7C70087FCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba2df3b5b203ed71146b9bab0fb3ec1177aa4d01","datavalue":{"value":{"entity-type":"item","numeric-id":4489170,"id":"Q4489170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a006945bed0e14c3742f8dd7cb89251203b7946","datavalue":{"value":{"amount":"+0.86057967","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q817778$AF9C271C-DC9C-449B-9C7D-CC8172BA47C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b51809de4b1700f28feec2b561b1106e0b1f7bff","datavalue":{"value":{"entity-type":"item","numeric-id":442317,"id":"Q442317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6cee18e50ee7d8a3b4906b32ffab20a8a51b74e","datavalue":{"value":{"amount":"+0.8502829","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q817778$D8AAE031-33AA-49DA-9747-0B70AD18397C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ef5227ee7a806a8bfa2b801c0031bd4ae60e1dd","datavalue":{"value":{"entity-type":"item","numeric-id":3646106,"id":"Q3646106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e52e990c59c86abcca8f120771369509c9381dec","datavalue":{"value":{"amount":"+0.84813815","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q817778$7C22781C-648B-44C2-B657-1672D2E799DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:817778","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:817778"}}}}}