{"entities":{"Q1297406":{"pageid":1308156,"ns":120,"title":"Item:Q1297406","lastrevid":70091265,"modified":"2026-04-13T12:23:00Z","type":"item","id":"Q1297406","labels":{"en":{"language":"en","value":"Distance graphs and the \\(T\\)-coloring problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1321772"}},"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":"Q1297406$EC7D1B3A-B1FA-49C3-82FB-0C33B02687B0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c0d35e268c65fa31c3623652829bb3a0bfa483e0","datavalue":{"value":{"text":"Distance graphs and the \\(T\\)-coloring problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1297406$6502FB5F-FF7A-40CE-8D83-587B09B14204","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6fae08bb8565396857d55cae939c6d2c9caa6e18","datavalue":{"value":"0932.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297406$B99458B9-D016-4687-8B9F-469FD93C108B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d981c9e0d54b37fe506541d541ccd03ebf326d78","datavalue":{"value":"10.1016/S0012-365X(98)00199-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297406$3DC59CD6-D1F6-4379-866F-C6CA5D1F6E56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd1037046058c2dfc0c0b1e877b414cbdbfb241c","datavalue":{"value":{"entity-type":"item","numeric-id":229340,"id":"Q229340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$F061C806-5192-4E4E-B33B-6C695E4F2EAE","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":"Q1297406$B3B19E7D-F97F-483F-91F6-E0202B0B3DE0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1b67edb7c6ba470465e19f8a68d18347f5f95336","datavalue":{"value":{"time":"+2000-02-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1297406$7BA27EA5-704C-439A-B015-E000DA9D270B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d4e406ce842a06b43bfbb47d8977e199830659c1","datavalue":{"value":"By the \\(T\\)-colouring problem we mean a generalized graph colouring problem which is one of the variants of the channel assignment problem in broadcast networks. The set \\(T\\) describes which channel distances are ``forbidden'' in order to prevent interference between transmitters. The \\(T\\)-colouring problem for complete graphs is equivalent to the clique problem for distance graphs. It is shown that (1) the \\(T\\)-colouring problem for complete graphs is NP-complete in the strong sense and (2) the ordered distance graphs can be recognized in polynomial time using linear programming techniques.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297406$34EAEFFE-D234-4D46-A6DB-1A39B7D881EC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297406$C688711D-A2EA-4B56-B3FF-4C9ABE66B9AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297406$B9117DF9-FA5B-4D84-A254-D728D756EAAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297406$EFD726C8-E9C5-4E5E-BB69-28B93A3CF1A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297406$FA2EF091-F3A1-4DAD-9143-C8B1FAB78FB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297406$11B974D7-1BAE-4A29-991B-4E8D11D9CED3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0e33f45843c84c145fc8599c857f57a456e3ce25","datavalue":{"value":"1321772","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297406$1B90C8FE-76ED-45A0-AEBB-00110545E589","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31f1bdb6856b9451cc7d0d2862c8fd16fe889e39","datavalue":{"value":"\\(T\\)-colouring problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297406$2163D596-D118-4DDF-A2D2-D2A56E58159E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"12786b5caed97ee9434da4381367aba30ea40d3c","datavalue":{"value":"distance graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297406$30A120F2-0A87-47E3-A4CC-DEC4F1EF9242","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fa01ee8d01fdc058743d4cb5961413365b30dd30","datavalue":{"value":{"entity-type":"item","numeric-id":587976,"id":"Q587976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$786D6808-9B49-43EB-AE7D-8E2C2C931B99","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":"Q1297406$E865ADAF-FB46-4DE6-AE98-C8FE108D88E6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7258962f550bf808b8ce0edfe0f9b2099a09d076","datavalue":{"value":{"entity-type":"item","numeric-id":4230322,"id":"Q4230322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$D68B5C37-D199-4FA5-8416-EAB3B6A6C852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f27e255315b978ff9d021b83498e6cce1a92902b","datavalue":{"value":{"entity-type":"item","numeric-id":1393438,"id":"Q1393438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$F20B719E-5147-4E3A-9223-63213C670676","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6e42f2a467ccdae7c9f05b9d349bc6c1025c1db","datavalue":{"value":{"entity-type":"item","numeric-id":5286940,"id":"Q5286940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$50914859-8B09-4956-84D3-A20F3F7F4E6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5182d1fd961dad30e0b7624eb6d6ad84ca60d22","datavalue":{"value":{"entity-type":"item","numeric-id":800371,"id":"Q800371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$B463A08C-A9C7-43C1-A623-4013BA7A40C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e7d3dffde4b639a5080d558096cb7a34be71d72","datavalue":{"value":{"entity-type":"item","numeric-id":4146529,"id":"Q4146529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$F8F1D696-D3FA-439B-A4DC-D14E2E1A229B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bc0395798c55c9b543d2ec7445c8d272e60cc5d","datavalue":{"value":{"entity-type":"item","numeric-id":5515488,"id":"Q5515488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$B88B46E0-24D5-4F91-A546-8C1FE0192BB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43933941143ee0993fa68b65eabdf09970b1e098","datavalue":{"value":{"entity-type":"item","numeric-id":1918544,"id":"Q1918544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$74D53D74-2CE6-4ABF-B2A2-C077A62EDA96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6701bea36bc4ea6cd4518a77918bccc0eacd91e","datavalue":{"value":{"entity-type":"item","numeric-id":5733654,"id":"Q5733654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$BBE6DD28-7A35-4C56-88DD-1AAC4A0C173D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0363418f97e59fb1936c27121e237a5c19ded3e7","datavalue":{"value":{"entity-type":"item","numeric-id":1197028,"id":"Q1197028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$63371130-66A2-4BB5-93D9-BD482718C1E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e6e0627601eb678357cd6a182e4c3a611cabaca","datavalue":{"value":{"entity-type":"item","numeric-id":1182897,"id":"Q1182897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$24AD52F4-6778-4088-87D5-D3BB96339335","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29c667f77963fc180fb6082858ff6af851d444ab","datavalue":{"value":{"entity-type":"item","numeric-id":4005786,"id":"Q4005786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297406$A3470AF8-0025-4EF4-964F-618F7BC020C5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2e0b17b01d01ee196ab791a0659f70f3ca41c48a","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(98)00199-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1297406$DAFD2BC4-AA19-40EB-A66B-45472CD828B7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"becbed54b039cb608bad9e07af8b242315967da5","datavalue":{"value":"W2003884459","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297406$68C293C5-A8AF-4943-B9E0-8BB0E38AF998","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7161b2d36a849d5db63498cc38d8ea4d2bf34bd0","datavalue":{"value":{"entity-type":"item","numeric-id":1305534,"id":"Q1305534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"092ef790924fea494b860c25453ca87e7eb380b9","datavalue":{"value":{"amount":"+0.98976994","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":"Q1297406$9B976A4C-5F42-48EE-8AAF-B3EB7CE44238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52e2f2b28ba956e7d05058987d760e289a7e7f18","datavalue":{"value":{"entity-type":"item","numeric-id":6070499,"id":"Q6070499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f2048d99223ca36fc17d251d51ad77ece76a67d","datavalue":{"value":{"amount":"+0.9566303","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":"Q1297406$D9A8D638-87B3-47B2-8755-72CDF2C88559","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1f37b1bf90da691cff71528b848d9f5e94e0d1a","datavalue":{"value":{"entity-type":"item","numeric-id":741239,"id":"Q741239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"195a281b738cb037424260af8b7a8b77ceeeb306","datavalue":{"value":{"amount":"+0.9555422","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":"Q1297406$2854FFE1-9EE5-4805-99B5-C3427FC33417","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a02d9e0d5cd8666350bc23ddedc7cf82c4748377","datavalue":{"value":{"entity-type":"item","numeric-id":4552213,"id":"Q4552213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a0869a7408f7be42ca1dfff3d6987fa361f9f3b","datavalue":{"value":{"amount":"+0.95179576","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":"Q1297406$EA6ED9A6-C36E-4932-9BAC-2109BEA0FF3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4bc3594b473aa8e271db712d4664a0cec71e89e","datavalue":{"value":{"entity-type":"item","numeric-id":2869363,"id":"Q2869363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2819eec6a35d2c3ed92fdbc0bea8f56c86c8ec8a","datavalue":{"value":{"amount":"+0.94910264","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":"Q1297406$FBA85907-07A5-47D1-AE9D-41967311DF2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ea710315cb366a52d65102f826a441b0bbbd6fd","datavalue":{"value":{"entity-type":"item","numeric-id":5313821,"id":"Q5313821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0aeb6edffe03cf5324cd35fd0eb2505cc1446fb","datavalue":{"value":{"amount":"+0.9447783","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":"Q1297406$C8C96A75-5A2C-4BFE-B06A-971A5CAAE3FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa2b480e0aeffea14e016cbc2ee214341d7b09f5","datavalue":{"value":{"entity-type":"item","numeric-id":4898707,"id":"Q4898707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"489f6ea98c11fbacfbbf0b65afc168d23a772a40","datavalue":{"value":{"amount":"+0.9419677","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":"Q1297406$A2D1A635-6100-4C99-8B11-FF49091A71FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e8d95f502984402b9ca00f1084c423c5503e4a6","datavalue":{"value":{"entity-type":"item","numeric-id":6166628,"id":"Q6166628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1610fb558dfe5ec004830ffdd54dea70817afd37","datavalue":{"value":{"amount":"+0.9353127","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":"Q1297406$BCA6BE5C-F0D2-49CD-88DD-905909046DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"079cd3398abd43c8117506635c5903f619133497","datavalue":{"value":{"entity-type":"item","numeric-id":2847920,"id":"Q2847920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c77ea778b7f4c3b4215bdbdc8bc1b9aeb2ae4bc","datavalue":{"value":{"amount":"+0.93475854","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":"Q1297406$E6864878-7C71-4365-B31E-0F012DE60A30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5718219044036149c880230d5c9fbc082f0083dd","datavalue":{"value":{"entity-type":"item","numeric-id":2760982,"id":"Q2760982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26c157547ae94a9cdc1ad2ec92857d44aeeb4763","datavalue":{"value":{"amount":"+0.9331882","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":"Q1297406$EE33A79D-1968-45F5-9C8C-BC712562CE05","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Distance graphs and the \\(T\\)-coloring problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Distance_graphs_and_the_%5C(T%5C)-coloring_problem"}}}}}