{"entities":{"Q2485944":{"pageid":2496687,"ns":120,"title":"Item:Q2485944","lastrevid":48523759,"modified":"2026-01-05T02:46:53Z","type":"item","id":"Q2485944","labels":{"en":{"language":"en","value":"A bound on the chromatic number of the square of a planar graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2192685"}},"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":"Q2485944$8A6A85F7-C8EC-42B6-BE9E-B98711E23138","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6053a355b6bc7e6d48d48cd50b717244695d164c","datavalue":{"value":{"text":"A bound on the chromatic number of the square of a planar graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2485944$CB6C97CE-7F12-4988-A077-B6FFDE172571","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"229c599bc9da523a8b3489df7df65db698d179d7","datavalue":{"value":"1071.05036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2485944$570CB595-F8CE-4241-96B0-4FD720863BA2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$54EB1E6F-77BA-457F-8F74-E617207193EC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$F9F5D261-7580-4C9B-B25C-BA58F3B7AD97","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"90b8e08a65c3f6b60302137bec886dcfcd8ff418","datavalue":{"value":{"time":"+2005-08-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2485944$C7B7E66E-D898-4A23-8EE8-0EBD4D7A2BB9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d64a854b63206147583b332bb57912db0aaaf522","datavalue":{"value":"http://hdl.handle.net/1807/9473","type":"string"},"datatype":"url"},"type":"statement","id":"Q2485944$C30C0E7E-5D76-4F3E-90BA-94A019F64169","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a9312d1d0efd34bde327cd2c7221a3c58becdf47","datavalue":{"value":"The well-known Wegner conjecture says that \\(\\chi(G^2)\\leq \\lceil{3\\over 2}\\Delta\\rceil+ 1\\), where \\(G^2\\) is the square of graph \\(G\\) with maximum vertex degree \\(\\Delta\\geq 8\\). The authors prove the following main results.   (1) For a planar graph \\(G\\), \\(\\chi(G^2)\\leq \\lceil{5\\over 3}\\Delta\\rceil+ 78\\).   (2) For a planar graph \\(G\\), if \\(\\Delta\\geq 241\\), then \\(\\chi(G^2)\\leq\\lceil{5\\over 3}\\Delta\\rceil+ 25\\).   They show how to transform the proof into a colouring algorithm which uses at most \\(\\lceil{5\\over 3}\\Delta\\rceil+ 78\\) colours. Since there are \\(O(n)\\) iterations of the main procedure, the total running time of the algorithm would be \\(O(n^2)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2485944$63C22651-9B15-45B9-9102-340B07A56601","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2485944$AA6099EA-80F1-48AB-878B-D482E6820FA3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6cbceba2d65f8a5a27e8a17657245db4f955d4f4","datavalue":{"value":"2192685","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2485944$C783DB56-9EC5-4EA9-9A74-5FAA0FBFC573","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"705bce76414898512ddfa0d08a811fc42ef6c4bf","datavalue":{"value":"Distance-2-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2485944$01BE1845-7909-433B-9CC8-D8495970CBB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"344eafeed357c3d2a25ea4e8790c7cf9ea5d37a1","datavalue":{"value":"Frequency channel assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q2485944$6DA72C51-D31C-4B13-9CE6-58E4894A79A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"163143c910566f1e3406472b0e4d7cf0b27aa817","datavalue":{"value":"Wegner's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2485944$0C0E7C6E-6EFD-4CA3-90ED-F7CC27DF6695","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":"Q2485944$40215940-2BCF-4B90-A49A-75B174AF60E5","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":"Q2485944$86662654-E59A-4C85-AB49-5A10E1D565DB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3467adf1c77cd5660c4175b4c41ed73550a74e9b","datavalue":{"value":"W2035278325","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2485944$93DC2C5E-8E00-43A7-9939-DFF4E7F32CBA","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":"Q2485944$3CD728F4-F5A7-4564-AFF9-CE2947DC965B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9328fd3a34fb4b6ce7887fc52cf1e0cdef518e43","datavalue":{"value":{"entity-type":"item","numeric-id":4097312,"id":"Q4097312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$0A8018D1-6B8D-4919-A07F-F4F57D92F55D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d6c290035bb317a16e7361307fd20aeb1e20a52","datavalue":{"value":{"entity-type":"item","numeric-id":4501549,"id":"Q4501549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$F743E4B6-A702-4872-B428-923389C5776C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a026cd0f4b7a301bb63b3a31e47f3cb40412d167","datavalue":{"value":{"entity-type":"item","numeric-id":4881295,"id":"Q4881295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$27AB5B4D-237B-458A-BE60-D1E691017A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddb1af92a25f2e947b618c76a23e659e5676798c","datavalue":{"value":{"entity-type":"item","numeric-id":3152424,"id":"Q3152424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$E8A59A8C-630E-4063-B5ED-B34E085435AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a5c994cc93aa4ede3a99ec090118a08485c3495","datavalue":{"value":{"entity-type":"item","numeric-id":3838194,"id":"Q3838194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$C2D4F6F6-63C3-4D88-9CC7-A1127F8FD714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a359527ed469944dfb2b879452c1c42adfdac53","datavalue":{"value":{"entity-type":"item","numeric-id":4879166,"id":"Q4879166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$8A754C5E-B4E0-4166-A2A9-C5AE6FF6C843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f38fa0195ddc4d1c845417fcaa2b34baf9c7cb0b","datavalue":{"value":{"entity-type":"item","numeric-id":4949819,"id":"Q4949819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$040B1F05-C1A4-4029-9706-C00ECAB54274","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":"Q2485944$B6E17977-73B1-4A94-8F2B-E9FEADEFFF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35184f581a4fa42ee779b59d5e27eea0c204219f","datavalue":{"value":{"entity-type":"item","numeric-id":5931450,"id":"Q5931450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$C30B3116-A844-4A9E-B676-612AB9D17709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9027db357e51a4c16fcbfde3213d5b3613fd480","datavalue":{"value":{"entity-type":"item","numeric-id":1850557,"id":"Q1850557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$974516D7-3685-42EF-8944-C4BEEC6E0BE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4e9c7040a510a4a56a7f3a400944ca0685c5831","datavalue":{"value":{"entity-type":"item","numeric-id":4242956,"id":"Q4242956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$8D5DCD87-A562-443F-9B55-3F348BFF9874","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":"Q2485944$FE311CDF-FD13-4BE6-BD71-346C2395A2AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c0bdc13b7ae115bf84ac5dc224b0b308b85c2c7","datavalue":{"value":{"entity-type":"item","numeric-id":4863972,"id":"Q4863972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2485944$278D4F48-3721-4A38-8D35-7436DF4AFDC8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d2622b81cf860897715bdd9c112970eb1e266b43","datavalue":{"value":"10.1016/J.JCTB.2004.12.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2485944$F12749A5-62CC-44D0-B76A-22D8ADE39E74","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2172b1238fdfdb2823e53274ba4fc91ab845c18","datavalue":{"value":{"entity-type":"item","numeric-id":3503513,"id":"Q3503513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d86faa2bff67e2b5feafc9e2bdb1a59dce5ab054","datavalue":{"value":{"amount":"+0.8949939012527466","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":"Q2485944$A6A64F10-53EF-4F38-8D58-6BE4B091514E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4459ca9270f19fa647b21f29a26dc4147d5c51a","datavalue":{"value":{"entity-type":"item","numeric-id":4797924,"id":"Q4797924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3a2173ef73ff880b2ed575b468aca319935caf2","datavalue":{"value":{"amount":"+0.8829125761985779","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":"Q2485944$63F7CDA0-C106-47A1-A60C-4F72D5F7BCC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7e9ec30573f3e83343f57c699573ae6d2cb2856","datavalue":{"value":{"entity-type":"item","numeric-id":2472571,"id":"Q2472571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a4ee291e03c9d74805fbf462092d3ac8182781c","datavalue":{"value":{"amount":"+0.8673178553581238","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":"Q2485944$31F00403-8576-4315-B395-F530A6515A29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a89eef62de083abca7b9a1fbca66f88edda5be3","datavalue":{"value":{"entity-type":"item","numeric-id":2824258,"id":"Q2824258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a8d681d927c8288822ed79a351822db58b0741d","datavalue":{"value":{"amount":"+0.8651586174964905","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":"Q2485944$D2D2D824-8F60-4B67-ACE8-B684A1A4A8DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75196e2eb2363cc6477446f6f4c9ce21c3c4e2d8","datavalue":{"value":{"entity-type":"item","numeric-id":1928491,"id":"Q1928491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"657c8eceb0844c333e7e5f934015bc6cf14aa860","datavalue":{"value":{"amount":"+0.8557083010673523","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":"Q2485944$CB7C96AC-EA6F-4098-8D83-1AA28E249258","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2485944","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2485944"}}}}}