{"entities":{"Q911612":{"pageid":913460,"ns":120,"title":"Item:Q911612","lastrevid":49367728,"modified":"2026-01-07T01:14:29Z","type":"item","id":"Q911612","labels":{"en":{"language":"en","value":"The effect of two cycles on the complexity of colourings by directed graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4142067"}},"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":"Q911612$2A677BDD-22BC-4BD0-8A0D-B11ED6769EFA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f1156525b63309ab3c5928a7a3f0c3bbb17e9b59","datavalue":{"value":{"text":"The effect of two cycles on the complexity of colourings by directed graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q911612$94D04CE4-C1AC-4A13-8B27-5B265E7D43A0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"33b17de2ab30cde230384ca49183108c74a698c9","datavalue":{"value":"0697.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911612$CD6498F2-8C68-4854-AD9A-78880B2077C1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b8563ff9af70bf3dc4422e4aa4e33c2bcef27b7f","datavalue":{"value":"10.1016/0166-218X(90)90017-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911612$B0BF55B0-8F57-4691-AA47-46C917517EAB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$69B34C9B-202D-4835-B0E4-C68F3F4A513E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q911612$8EB25F06-8165-41B8-B5FD-E1280FFD6E27","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f0c0dcc5102ab123d79a81c98e30cb3e8155fc9e","datavalue":{"value":"Let H be a fixed digraph. An H-colouring of a digraph D is a mapping f: V(D)\\(\\to V(H)\\) such that if xy is an arc in D then f(x)f(y) is an arc in H. The authors discuss various classes of digraphs H in which the existence of two directed cycles makes the H-colouring problem NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q911612$D0285612-FA5A-4BFB-8343-A1A81C91C7E1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911612$B71C0575-BB5D-4A3D-8270-A31D1127E5B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911612$7E641BCE-DC26-4924-9B1B-2950158452E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"77b2369746f0495bcfbd953c18ad01ed7dd609c6","datavalue":{"value":"4142067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911612$50517205-CF6B-4B74-8A8B-3E91871214FE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"def48283d510794913c58f78056b808e00633a5c","datavalue":{"value":"graph colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q911612$1C185B53-C761-44F0-8C84-9BB8500012B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffa219ea2cff89df5162edb57bd2a31ea73e1a26","datavalue":{"value":"digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q911612$079D6994-6FBE-439C-98A6-961641CFD26D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40e9513c4e12f0204669d7142326a7f04618799b","datavalue":{"value":"directed cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q911612$072EEC71-6A6A-429B-A5BC-3A1B443BFFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed4471abeaa377fd1e9fa25361a2707c68bdbde0","datavalue":{"value":"H-colouring problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q911612$4E2C3D3C-9E22-4F95-91F7-F10D3634612D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q911612$3B48384D-B97F-4FDE-8FC7-2F350C0D838F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f64c4b091272c660c279938fc740575735afef58","datavalue":{"value":{"entity-type":"item","numeric-id":558237,"id":"Q558237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$4E7C71B0-314F-4921-A37F-78C9B90DA999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3b5375d01a59455d415f2afee9796bf93e2b3c4","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$8539774D-34D5-4496-8412-3593E27907C2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"478bb984958f47159570b1788ede69358a5f4226","datavalue":{"value":{"entity-type":"item","numeric-id":656146,"id":"Q656146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$23137278-9475-474A-ACEE-BB3CA453EF9C","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":"Q911612$2A5FE655-8F4D-41B5-86ED-C851216330CA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"24503c715080e90c80139adbb12057695f60fcf9","datavalue":{"value":{"entity-type":"item","numeric-id":3758851,"id":"Q3758851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$3DB7031C-9ADC-4C2D-9C68-C87480812D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ca92c5e9c033964322f96db99eac2d4a15c7ec0","datavalue":{"value":{"entity-type":"item","numeric-id":3834066,"id":"Q3834066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$641A9757-F9FA-4368-AF62-34D761F60A73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98b621b31f596378d337a5257f1b9f1e39adfddc","datavalue":{"value":{"entity-type":"item","numeric-id":686279,"id":"Q686279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$150E8616-2485-4D60-9F06-5CB6C3494068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e18975fbe96343fc0c778502af0d8435c15ebc5","datavalue":{"value":{"entity-type":"item","numeric-id":1842146,"id":"Q1842146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$270B277B-628A-4992-95AF-416A9D315F5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a253dfedc634c3617fd93c34bc6b364162d4ecb1","datavalue":{"value":{"entity-type":"item","numeric-id":3791169,"id":"Q3791169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$FE814266-4E9C-402C-91E6-91C0CADA3CB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$0C31F10B-A3F6-4D02-A652-C1EFADF9E52A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5028065ceb61d7fbbcc8d74c873e6a965e0cc43f","datavalue":{"value":{"entity-type":"item","numeric-id":1110530,"id":"Q1110530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$8144F315-9893-47F5-B205-F729CCE25E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8002546a42d967ab22805fe7698fd4d1aa8f6401","datavalue":{"value":{"entity-type":"item","numeric-id":3968465,"id":"Q3968465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$B53B915E-D8E9-4E8B-BB99-5A31004AC821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01874425d018f2c41712bb3fb8e538c43c3a3a01","datavalue":{"value":{"entity-type":"item","numeric-id":1250117,"id":"Q1250117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911612$5AAAD592-B726-44C6-BA46-6845A357B3D0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0fdce2772dcefa1d912d0994db29a4f50fe699bf","datavalue":{"value":"https://doi.org/10.1016/0166-218x(90)90017-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q911612$E4F9E523-E2EC-4415-A191-6CC2FED9C12E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bc5ac19c9f4a95cb725203fb4dd92e75e0f6c324","datavalue":{"value":"W2021465457","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911612$CAB5DFC1-6DF0-433F-AFF5-6E0CB4A476BA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd0e3843b600990de3a46824528772dbf1995a46","datavalue":{"value":{"entity-type":"item","numeric-id":3987041,"id":"Q3987041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25315c8021e74e9e506159c6729e2536ab91c618","datavalue":{"value":{"amount":"+0.9160895347595216","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":"Q911612$F44EF34E-F1C2-4F8B-A3D8-04106FBD6A76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a089b9ea92836fdb3b9970422c3a35f016894b00","datavalue":{"value":{"entity-type":"item","numeric-id":686279,"id":"Q686279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13e2ca82ca92007cb62e3085a02135647afba6ac","datavalue":{"value":{"amount":"+0.9159530401229858","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":"Q911612$A9947E97-88FC-4E40-887A-14A12B72B43F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cbdd1bead25b630c2d47d1edc692caf2800960b","datavalue":{"value":{"entity-type":"item","numeric-id":4873684,"id":"Q4873684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7023c7d16cbcccc6a11fd65c22930ddc1bdcc808","datavalue":{"value":{"amount":"+0.8946975469589233","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":"Q911612$8B80F63C-AC15-44B8-B6C5-2A24CC1752E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38773e3d51d65506ff3b07036d5403578a6749be","datavalue":{"value":{"entity-type":"item","numeric-id":3834066,"id":"Q3834066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22596d476833c4bcd95596377d3cdcfa490c7543","datavalue":{"value":{"amount":"+0.8799682259559631","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":"Q911612$5830D867-EB2F-47C0-AF29-9F83C659F72A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40eea57eb116ad49129f868e1ee17276c4a6810b","datavalue":{"value":{"entity-type":"item","numeric-id":1842146,"id":"Q1842146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d86463862909bb51cfea3aba5d2064e66a9f4bd","datavalue":{"value":{"amount":"+0.8711024522781372","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":"Q911612$A07F37E0-2ADE-4566-881B-15DCF200BAC4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:911612","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:911612"}}}}}