{"entities":{"Q5936032":{"pageid":8112834,"ns":120,"title":"Item:Q5936032","lastrevid":41928454,"modified":"2025-05-16T12:37:42Z","type":"item","id":"Q5936032","labels":{"en":{"language":"en","value":"Channel assignment and multicolouring of the induced subgraphs of the triangular lattice"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1612892"}},"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":"Q5936032$173482FF-0AA5-42ED-80A9-2EF5C70EBB4F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7881f39ba5add94930b31608eb0386afca46525a","datavalue":{"value":{"text":"Channel assignment and multicolouring of the induced subgraphs of the triangular lattice","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5936032$7D2A604D-16EF-4607-AA3C-200AEA8C0371","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ae8c74d6a2897a8c7f1fe8c32fca09af9c6cafdc","datavalue":{"value":"0983.05031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936032$A821EEEA-5E5C-4BF5-9D8A-02B75BF5E040","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ad9c84716061e515710f4116cc3aea7cecb9fec0","datavalue":{"value":"10.1016/S0012-365X(00)00241-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936032$EA3615EB-3636-4B50-8AD6-DABAD5A61B5E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4e8471076b9574779be9b69bcf04a02e8ebd18d","datavalue":{"value":{"entity-type":"item","numeric-id":186133,"id":"Q186133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936032$D550F42C-14D2-4005-A836-1025CAFB9595","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":"Q5936032$B4372885-DEF5-4E7B-BBDF-4CA4D4B05DEC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2c5af00fd1fc149dba1e61ff5498f18aaaa6efa9","datavalue":{"value":{"time":"+2002-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5936032$FAD79FAE-061E-4B54-A703-B228D5333687","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d4de3193b89da1a841d76ad5faa949e9be96ad30","datavalue":{"value":{"entity-type":"item","numeric-id":228803,"id":"Q228803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936032$D8C89A1E-205B-4E48-AA99-7F170C87EB6F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936032$5D518084-40B1-4CE7-A705-11967C613F93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936032$96F9DD12-0DE8-46E9-9A5C-654F743B5BE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936032$D2521038-9F1A-4EC0-ADAD-AD4B67C2B298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936032$4E0720FB-0BE5-45C1-B9C4-C7CD6D9F386C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2f4e1ebebf0d41f0c0ac0ad548ae41d00ac454bf","datavalue":{"value":"1612892","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936032$607C259F-929E-4965-B0AB-7CBE405B4AFA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d63b2870dc0b8798d5777f30104f465aa175be2f","datavalue":{"value":"triangular lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936032$1ACB9359-CBD6-46AC-A6C7-CA9BC0396427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a966cad9a5db0c692a58829c2f47a3a1adfc56c","datavalue":{"value":"multicolouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936032$CFA96ADE-37DB-4798-95C9-ABDFC1FAE3B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb4dbee0d48d17c0702756f23f68f3af28651233","datavalue":{"value":"induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936032$B4618AF3-01F8-4A42-B038-15473724DC9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77ace25a638e56e6fa7da46ca9b6aaa0863b538d","datavalue":{"value":"channel assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936032$10939FB2-DF18-47AA-A485-614B48E156DC","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":"Q5936032$CB65AD29-6927-4B50-A033-312EE11F02F6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"586e4192377f2eb4e24d4177d4ffffe7b494f77e","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00241-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q5936032$34725F0B-F8B2-485B-96BA-832B6C37F5DE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c5bf02f8ce4ea8b6b60fd80abf4bcd05b6b7696c","datavalue":{"value":"W2074755942","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936032$89DB402A-2F6C-41BB-89D8-5A737C45D2EB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce09aaf6a09fca25f4085601a4db003c96169b59","datavalue":{"value":{"entity-type":"item","numeric-id":2570123,"id":"Q2570123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af026093f7e510f312fae614a5f0da90e15e6c64","datavalue":{"value":{"amount":"+0.82567394","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936032$0E4F7914-FDE3-4E91-8A6F-BA4A0306E4C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56bb9e5ab9c08358b03077f2aca5c5924c917ee8","datavalue":{"value":{"entity-type":"item","numeric-id":1349081,"id":"Q1349081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a08124d658a1032df40dd61f25f473523a617430","datavalue":{"value":{"amount":"+0.7820528","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936032$28D8F4A0-6EAC-47F6-B994-029922F81079","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c7914fbb5d4044144db87d39b13e01da7d6c1b6","datavalue":{"value":{"entity-type":"item","numeric-id":752722,"id":"Q752722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61b9927e684087b930be8985f53ec24044856fb4","datavalue":{"value":{"amount":"+0.7692569","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936032$9F377AE5-40A9-4D06-B87D-852A4E3B88DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a03859512a19c8db823714170e6720556311cc2","datavalue":{"value":{"entity-type":"item","numeric-id":3439400,"id":"Q3439400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0825e5700ba4d6d3efa84501a8acfc9507d7b6af","datavalue":{"value":{"amount":"+0.7589776","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936032$7B8DE265-986B-4C7B-9F17-C8A2F9966678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"714527e2760e566c706e4e8a73a5cc9a82a693b8","datavalue":{"value":{"entity-type":"item","numeric-id":4519133,"id":"Q4519133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d6c4fd663097a1a8628e9095321cb2a4cfb0622","datavalue":{"value":{"amount":"+0.7571088","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936032$5707BEE3-88E3-427F-BEE3-CE95A1B9F472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca1732f4b01e91fb531fbbc27abd3a241bf352f7","datavalue":{"value":{"entity-type":"item","numeric-id":658035,"id":"Q658035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"481c542176d47178418316e3962738181c021052","datavalue":{"value":{"amount":"+0.7570431","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936032$B1A7AEFD-43FE-4B1A-BE4E-974145416473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ad6254d3b58d2b6329d1fbfb9cb8c1f1dfca74b","datavalue":{"value":{"entity-type":"item","numeric-id":3070330,"id":"Q3070330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38208490854aa20dd89dcebde559bb48f607d728","datavalue":{"value":{"amount":"+0.7551378","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936032$BBC84E7C-EE87-4B80-BFA9-633F75BC36B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f9511611e586790b66f8b0a3a9661a009b55ebd","datavalue":{"value":{"entity-type":"item","numeric-id":5930155,"id":"Q5930155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3da55839c09682f8d625a2a7113a0ec86b35aadf","datavalue":{"value":{"amount":"+0.7437629","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936032$DE8439B1-A1D8-498C-B680-41B14E99BD95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f830075f1a01212b82ecff2875db00582da34a8","datavalue":{"value":{"entity-type":"item","numeric-id":1297436,"id":"Q1297436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ed499a420fde2b0dd17c5cb12c98f651dfdeed2","datavalue":{"value":{"amount":"+0.7427638","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936032$DFE30666-F54D-4561-98E5-876FA91DC85E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"654fcfdeec206b4653e88e46cb51b3549c8bd4ea","datavalue":{"value":{"entity-type":"item","numeric-id":5710015,"id":"Q5710015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da0da9d98a59986ebd583ed28623b0085c8b4fc2","datavalue":{"value":{"amount":"+0.74181134","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936032$40AEBA72-CB46-41C2-ADD6-6EC2C7B0EA4B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6c0383a0efa6a0f87852f7a191d56e394829d4fd","datavalue":{"value":"Motivated by a real-world problem in mobile telecommunication, the main issue of the paper is a graph multicolouring problem. Let \\(G\\) be a finite triangle-free induced subgraph of the planar triangular grid and \\(k\\) be a natural number. We want to \\(k\\)-multicolour \\(G\\), that is to assign a set of \\(k\\) colours to each vertex of \\(G\\) so that adjacent vertices receive disjoint colour-sets. This task resembles the channel assignment problem for transmitters in a mobile telephone network. NEWLINENEWLINENEWLINEThe \\([k]\\)-chromatic number \\(\\chi_k(G)\\) of a graph \\(G\\) is the least natural number \\(n\\) so that there is a \\(k\\)-multicolouring of \\(G\\) using colours only from \\(\\{1,2,\\dots,n\\}\\). McDiarmid and Reed conjectured that for any triangle-free induced subgraph \\(G\\) of the planar triangular lattice we have \\(\\chi_k(G)\\leq\\lceil\\frac{9k}{4}\\rceil\\) [see \\textit{C. McDiarmid} and \\textit{B. Reed}, Networks 36, No. 2, 114-117 (2000; Zbl 0971.90100)]. To prove the conjecture, it would suffice to prove that any such graph can be \\(4\\)-multicoloured with only \\(9\\) colours. The author proves two weaker statements: any such graph can be \\(2\\)-multicoloured with \\(5\\) colours, and \\(3\\)-multicoloured with \\(7\\) colours. This latter theorem implies the main result of the paper, namely that \\(\\chi_k(G)\\leq\\lceil\\frac{7k}{3}\\rceil\\) provided \\(G\\) is a triangle-free induced subgraph of the planar triangular lattice.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936032$D2B6F95C-E1F1-4F45-9C3B-095B0576297B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5936032","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5936032"}}}}}