{"entities":{"Q709314":{"pageid":711163,"ns":120,"title":"Item:Q709314","lastrevid":63706806,"modified":"2026-04-11T15:00:07Z","type":"item","id":"Q709314","labels":{"en":{"language":"en","value":"The complexity of colouring by locally semicomplete digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5801211"}},"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":"Q709314$947EF7FD-6F03-4F8A-9EB5-27AA112EB860","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2f0503196bd23251b68edff967514de30b4acde2","datavalue":{"value":{"text":"The complexity of colouring by locally semicomplete digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q709314$98CAD0CA-DE33-42D8-8815-2E6B55EACD34","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8effd28274ad8dc53095e27115078c364392bffd","datavalue":{"value":"1221.05173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q709314$DD949FA8-C547-4F6B-BB93-45957A4692A8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"57555e49e581043524b19e8ff224491cb25ceec4","datavalue":{"value":{"entity-type":"item","numeric-id":189757,"id":"Q189757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q709314$6823910E-3FDA-465D-8C85-F1DCCA346CAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"94ab8ff74856f4bf7555f8daa1e2f7d2d31c5a21","datavalue":{"value":{"entity-type":"item","numeric-id":709313,"id":"Q709313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q709314$3F94AD6C-803D-43B0-8445-44AB46DE58D0","rank":"normal"},{"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":"Q709314$DDB26CFF-2092-414E-BB50-0264F7DE9786","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q709314$A8812CD9-1D4A-4058-960C-D687FD2E48A6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ec811f7b03455a8262cc40bbef90485dcee8ad13","datavalue":{"value":{"time":"+2010-10-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q709314$DA5E585C-4461-45F7-A4F7-F8285343CDA1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q709314$B7D610EE-15A3-4B50-BB22-4F003A2A7FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q709314$AECD475B-CCF3-4B2E-92C1-E57D4156DC70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q709314$49BDF067-197D-4320-98E9-49F10FAC7787","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8ecff5f882fea9a1a3b54bd421159d193f652be2","datavalue":{"value":"5801211","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q709314$0FD53A23-3492-4324-B352-AAD792A00D4D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1fc28d409ba9247115c9615ac90720a96398fee","datavalue":{"value":"digraph homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q709314$2427CE87-2E95-4769-A69C-627FAFB29B8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q709314$8D5C4B49-57D0-483F-9F4A-94E8A67BDFB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q709314$E6A8FC33-E78D-4165-AAEA-B0965E8FB035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q709314$B198FEBA-AA55-45DA-B9BC-4910703B2D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e92255abe1c6d7e27e81da39456bb7b7ff309c40","datavalue":{"value":"locally semicomplete digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q709314$409EE8CB-7A2E-4C89-B887-04D484943205","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":"Q709314$F5202089-39D3-4AB1-86BE-E0CD7F5C3694","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"979efa16f1d9c658d448c2269a3860d0e932e9ac","datavalue":{"value":"https://doi.org/10.1016/j.disc.2010.03.033","type":"string"},"datatype":"url"},"type":"statement","id":"Q709314$62A5E110-DF56-40B2-A820-C80AD13A6C5C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5f556c1a3569a3759141bea50dfd1c559f1276d1","datavalue":{"value":"W2036553843","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q709314$79C800EC-0822-43F0-849A-8E36F4273B90","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"11507e1d60ec78e27574307e67a23889371ace33","datavalue":{"value":{"entity-type":"item","numeric-id":3481724,"id":"Q3481724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q709314$1C940A4F-F7E3-47E2-B14B-730F310637B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2481155a42676d821e036db9e722c8d7abd317aa","datavalue":{"value":{"entity-type":"item","numeric-id":5502988,"id":"Q5502988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q709314$DCAB57BC-4749-4B36-B1DF-73B64AB97DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ade5a5172a0b2dc9f519d61c7175134ee8bc199","datavalue":{"value":{"entity-type":"item","numeric-id":911612,"id":"Q911612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q709314$CD33965D-1E99-4694-B2B1-4E340DDFD41D","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":"Q709314$6D1324C1-2E0B-4949-93CA-FBA1222D00D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf0113f702b668b1200acbbad87bb5793570f94c","datavalue":{"value":{"entity-type":"item","numeric-id":5499919,"id":"Q5499919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q709314$339C1311-F36D-4419-A1E9-8F0A12C7BC20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fcc1beb258313c6cc88cda9ae62d481e75d9884","datavalue":{"value":{"entity-type":"item","numeric-id":3642864,"id":"Q3642864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q709314$CFFCFB40-55D6-4D7F-ABD9-7644D449DBCC","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":"Q709314$A64F3D67-2335-4FFB-880A-F563C46D474E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b71ebcf94b7d9f1900f711045d833ef13e14fe33","datavalue":{"value":{"entity-type":"item","numeric-id":1183345,"id":"Q1183345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q709314$22266924-6A42-462F-B667-74AAAF8EBFAC","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":"Q709314$0CBA74EE-3589-4E49-A184-B67CD00BDB4A","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":"Q709314$F840FC4E-ECBF-4C87-BDF3-F68C8F00E510","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51c4e861d3a3225e8a2c2e7ba10ac8c959e9a32f","datavalue":{"value":{"entity-type":"item","numeric-id":4857446,"id":"Q4857446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q709314$E59D9711-BAB3-48C2-9A51-75391C28DD70","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6a13df5634266b95c522d8a0d27c16b5db8fab65","datavalue":{"value":"10.1016/J.DISC.2010.03.033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q709314$2E4808B2-C1D8-4659-9F03-9263C0A7FF0B","rank":"normal"}],"P1643":[{"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":"31f7837cc6e40e9d959ec347c3ad68e91d78d884","datavalue":{"value":{"amount":"+0.857571542263031","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":"Q709314$8EDB36BB-D058-47DE-841C-F296A17B0C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65ae0959436711b2a7a54fd98033e1442c5ffe7d","datavalue":{"value":{"entity-type":"item","numeric-id":2492190,"id":"Q2492190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79e210d6d39907047cea44f5569a9b18a881332f","datavalue":{"value":{"amount":"+0.8252081274986267","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":"Q709314$A4C95300-86CF-4965-BE68-35585269D4CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8525cf9f23a918a46a0caa944bd0e7ed01d6724","datavalue":{"value":{"entity-type":"item","numeric-id":5499919,"id":"Q5499919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39d9f23c2128d931fbf6def0c954e6982cb4c796","datavalue":{"value":{"amount":"+0.8199360966682434","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":"Q709314$1246FC7B-605A-4468-92AB-919D01E8E13F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3c98118c09642df1a04674400fa8d0728e097d4","datavalue":{"value":{"entity-type":"item","numeric-id":2674564,"id":"Q2674564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b80e0a1f9840879c59f75463c682675ae42ff2b","datavalue":{"value":{"amount":"+0.8067823052406311","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":"Q709314$62F65BDD-3DBB-44BF-8586-67FDC84388A0","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":"39d67a56325be9e28642fdb8fe75a8141ab4b2ac","datavalue":{"value":{"amount":"+0.805444061756134","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":"Q709314$AA7A16CC-DCE2-4A34-8BCB-3E77AA42042B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of colouring by locally semicomplete digraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_colouring_by_locally_semicomplete_digraphs"}}}}}