{"entities":{"Q724734":{"pageid":726583,"ns":120,"title":"Item:Q724734","lastrevid":63849858,"modified":"2026-04-11T15:58:03Z","type":"item","id":"Q724734","labels":{"en":{"language":"en","value":"Minimum 2-distance coloring of planar graphs and channel assignment"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6910542"}},"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":"Q724734$40275D51-18CF-453C-A970-B79B98DAF6F7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"975225265162e67fe775657e8652488d36cec7e7","datavalue":{"value":{"text":"Minimum 2-distance coloring of planar graphs and channel assignment","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q724734$39D657DD-A233-4BD8-A1F1-213E7E190912","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b2aa703527e0fb4649c39e91e5bacc69f683f518","datavalue":{"value":"1400.05092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q724734$6217D2E8-3D3A-4181-8E23-9BA561AE86B4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5c2ca19bbb7458a3ff59ad7dfa87f748eb36b1db","datavalue":{"value":{"entity-type":"item","numeric-id":369795,"id":"Q369795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$B6D4059B-51C2-4842-AF4E-192635E28E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9329971179cd1cf38774a499cf6b46db0ee9ba5e","datavalue":{"value":{"entity-type":"item","numeric-id":328714,"id":"Q328714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$A53EAC9E-DC00-4539-90D4-BB3FA7999037","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dcf8815e3b257674fa147da7a4e7c92c91c0b3e3","datavalue":{"value":{"entity-type":"item","numeric-id":185429,"id":"Q185429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$57929C0F-A4C9-4779-92A7-C15010A998E5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c11ebaf7be0aa0574d40db26aec7772df0b741f","datavalue":{"value":{"time":"+2018-07-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q724734$598413CA-0BB0-4DB0-8E94-578AA7429F1A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"150887f7f8e173c76ab2b23652ade36889017903","datavalue":{"value":"A 2-distance \\(k\\)-coloring of a graph \\(G\\) is a \\(k\\)-coloring such that any two distinct vertices at distance at most two get different colors. This coloring naturally arises from a problem known as the channel assignment problem. The minimum number of colors needed for such a coloring is called the 2-distance chromatic number and denoted as \\(\\chi_2(G)\\). For planar graphs this number was firstly investigated in [\\textit{G. Wegner}, Graphs with given diameter and a coloring problem. Techn. Rep., Univ. Dortmund (1977)]. Later, many other results and conjectures were presented.  As the main results of this paper, the authors prove the following two theorems.  Theorem 1. If \\(G\\) is a planar graph with maximum degree \\(\\Delta \\leq 5\\), then \\(\\chi_2(G) \\leq 20\\).  Theorem 2. If \\(G\\) is a planar graph with maximum degree \\(\\Delta \\geq 6\\), then \\(\\chi_2(G) \\leq 5 \\Delta -7\\).  Both theorems are proved by induction on the number of vertices and edges. In particular, some properties of a counterexample with the smallest number of vertices and edges are first investigated in both proofs. Then, a weight function \\(w\\) is defined on the vertices and faces of the graph. Finally, some discharging rules are defined to redistribute these weights. When the discharging is finished, a new weight is obtained and an obvious contradiction occurs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q724734$AE5BABBB-09CD-4C3F-AA43-5C1CA180D445","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"95df86062d8124e0d9be10bb6e6f66c634bcfc73","datavalue":{"value":{"entity-type":"item","numeric-id":298089,"id":"Q298089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$A3E76D87-CE4C-4CB5-B1CC-B8E440752AF4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q724734$470575B6-D333-4BB7-A771-52C84293C87E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q724734$989DC34B-D5DA-44B0-BA00-09911B38B8F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q724734$13F77CD7-C1EA-4A08-935A-168453AEFFD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q724734$8B121CE6-EF04-4792-9E0B-74B579197A22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q724734$DD8CE2FE-F842-494E-AC1F-E65544926CA5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"535d46acf82b9f6982bc08fdc33a8b9f1ac361ed","datavalue":{"value":"6910542","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q724734$E0B2BE82-A04E-4523-A994-B4ED1C1C0A78","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72161939e3ad72068bbe13f92562e74802ba304b","datavalue":{"value":"2-distance coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q724734$3903AD4C-C57A-41CB-9E78-F2FB57D0BFF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q724734$D6810A75-947A-425A-9F35-5CDCCE76CBF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q724734$3F57632E-C7A4-4704-AADE-B397D07A4BCA","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":"Q724734$568DBAC4-A917-4D54-ACD0-67B70C1AC061","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"caa19fc9c0e834cb1f111797a06edc63d33db8a7","datavalue":{"value":"https://doi.org/10.1007/s10878-018-0285-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q724734$C14F1FF4-7BC7-4BE4-99E4-78441E23DCCD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"04aca980d0b8b24678e3e3b6341083a9d3b2ddfb","datavalue":{"value":"W2795359627","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q724734$5C7FA2AC-1EFB-4EBC-9810-DA49561BB1DF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d8ca019d7aede39b5d91de165a428f108430e57","datavalue":{"value":{"entity-type":"item","numeric-id":4443117,"id":"Q4443117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$3EBA1851-AFA1-4B55-BBBB-30E24BA3D6DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$756DE285-9AE9-4C4E-A764-D2702D52D725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8d8116946752d3ce446be549aef6c7b01f93bce","datavalue":{"value":{"entity-type":"item","numeric-id":3178167,"id":"Q3178167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$29E5893A-BB47-4F1D-BAAD-7C0946643BF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ece0ba8be9384b2e3c6f2155568c8b171ab2821","datavalue":{"value":{"entity-type":"item","numeric-id":844207,"id":"Q844207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$D13B29DE-F243-40D3-B79D-46509C87AC1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fe02486500eee73f6860bf014eb4a5dc1368182","datavalue":{"value":{"entity-type":"item","numeric-id":2966513,"id":"Q2966513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$7231C691-B0B0-4815-8957-F8A09CC1460A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a415e76a6c4dfffab8c5043c692bae1e05da99b","datavalue":{"value":{"entity-type":"item","numeric-id":4030197,"id":"Q4030197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$6FF6B9F9-F31A-4FED-B541-D4227585E1ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2dcd19a03014335d79842ee4ced55daecaa909","datavalue":{"value":{"entity-type":"item","numeric-id":4797924,"id":"Q4797924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$231FC697-1B2B-4353-A44E-118571BA029B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c68b0e4aa46908a8b0f9e130d88ef24d2ea3157","datavalue":{"value":{"entity-type":"item","numeric-id":2966511,"id":"Q2966511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$66E849C3-3DA9-4822-999B-94D3B6F68C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b0e234e4550fe57438079adc504655133a6019b","datavalue":{"value":{"entity-type":"item","numeric-id":5367524,"id":"Q5367524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$6A828956-A821-499D-8FA0-787291AD9766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b14521108b62514cf2d9bd011b5a4e10da57ee9","datavalue":{"value":{"entity-type":"item","numeric-id":2788715,"id":"Q2788715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$AB9C408F-C86B-4345-A9B6-D7B2DE8FB119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5763401a400275883d373fb2cb7e9062551b4b86","datavalue":{"value":{"entity-type":"item","numeric-id":2485944,"id":"Q2485944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q724734$C9F7F6F4-C864-47A8-9747-C0007F4353F6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a946babbd79bf7b6a5b2b2723a0ba2b0bf847271","datavalue":{"value":"10.1007/S10878-018-0285-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q724734$6C355BEE-DC03-4381-8088-BC54EB1B1119","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"158c0c50dff5edd87847e878d1ce9ee9f12d1aaa","datavalue":{"value":{"entity-type":"item","numeric-id":2151384,"id":"Q2151384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce6c333a70382add709b4f227ce0cb49a7cf2133","datavalue":{"value":{"amount":"+0.9118109345436096","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":"Q724734$43779287-69BD-4C32-A819-3ABC91CEFE9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71de60f29b64f5d02e847800ab09340ed6b71942","datavalue":{"value":{"entity-type":"item","numeric-id":2075520,"id":"Q2075520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d34d9fdeafdb9da46a3fe2f5ac242ce91ca38469","datavalue":{"value":{"amount":"+0.9070175290107728","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":"Q724734$F473172C-D6BD-4F58-88BD-272624A8F9F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a7c8c161e7692324081aa53f4b50bf7aaa83023","datavalue":{"value":{"entity-type":"item","numeric-id":2152439,"id":"Q2152439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc21948922e6d5aa9d32169eb532561becb617a0","datavalue":{"value":{"amount":"+0.9032581448554992","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":"Q724734$E0774DC1-EF76-4670-8CD3-EC20650388F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"893b144e053b1f8cdb7e23033c6846c9fbe527f8","datavalue":{"value":{"entity-type":"item","numeric-id":1631690,"id":"Q1631690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db3046c9c2fc0570fe58ac084b87338ca8827692","datavalue":{"value":{"amount":"+0.8791771531105042","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":"Q724734$1FFD2CA5-D52C-48F4-A532-FF0E92951876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"323fc13b3e450f509c2105dcf0811309e1e8f446","datavalue":{"value":{"entity-type":"item","numeric-id":5017763,"id":"Q5017763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"269c17b904cb12381e869f80ca6f5bbbf14aaee6","datavalue":{"value":{"amount":"+0.8776528239250183","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":"Q724734$0ECEAD49-E760-4390-980F-E1D58B9C14C6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum 2-distance coloring of planar graphs and channel assignment","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum_2-distance_coloring_of_planar_graphs_and_channel_assignment"}}}}}