{"entities":{"Q1953438":{"pageid":1964180,"ns":120,"title":"Item:Q1953438","lastrevid":57617349,"modified":"2026-03-31T15:43:49Z","type":"item","id":"Q1953438","labels":{"en":{"language":"en","value":"Nonrepetitive colourings of planar graphs with \\(O(\\log n)\\) colours"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6171890"}},"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":"Q1953438$DA23B012-26F6-40AD-A211-0A7AC0B8689B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b7f2ab2d8d1f96953b665a6e2d737218bbd5581b","datavalue":{"value":{"text":"Nonrepetitive colourings of planar graphs with \\(O(\\log n)\\) colours","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1953438$61FFE634-12CD-42C3-ABE7-8F6E5C734260","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5df62459651249eac43a82feafaf1302adfa992f","datavalue":{"value":"1266.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953438$F58986EE-24B7-4DD5-A0DB-957B59410148","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb1d48e699dcbd07426b1c3ee3831813e5c5d7b0","datavalue":{"value":{"entity-type":"item","numeric-id":412238,"id":"Q412238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953438$BB3D7CD8-554D-4B65-935C-3D00F1312675","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4359076cb0a56591fe59bc08352dadec47996c6","datavalue":{"value":{"entity-type":"item","numeric-id":390120,"id":"Q390120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953438$F8AE07FF-C76E-4D94-ABD0-2CAF9639B33F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"88de6ea3aec65de7fd5bea5219c0d3561ce4c989","datavalue":{"value":{"entity-type":"item","numeric-id":259169,"id":"Q259169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953438$6F01660E-3D6D-4BA7-BA2A-E1493903BAFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"34323737e65ec23e5b5f138b40eff9f6aeba6f57","datavalue":{"value":{"entity-type":"item","numeric-id":390138,"id":"Q390138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953438$65E596E2-FB35-43B3-A300-F25C701F2160","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953438$DB228D66-0D45-4CEC-9B95-5FC1D5AF30FE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4a8303ee696998ba030c9b1c3b6bc07c6038c334","datavalue":{"value":{"time":"+2013-06-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1953438$5FAA6B62-955E-4521-9EA2-C406460EC7C6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"af37e381d74daef711a96b236bc132e022b14399","datavalue":{"value":"https://arxiv.org/abs/1202.1569","type":"string"},"datatype":"url"},"type":"statement","id":"Q1953438$42DBB1AF-CE83-4D40-93CD-3A11EB3A03A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"f624d064a943ce72afb3df8ebfb49d2dfa634824","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p51","type":"string"},"datatype":"url"},"type":"statement","id":"Q1953438$2A83C315-9883-4790-86BA-77BF62A225A3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0f64bcfe99304e7dda45738138e2a3a8cc1252be","datavalue":{"value":"Summary: A vertex colouring of a graph is nonrepetitive if there is no path for which the first half of the path is assigned the same sequence of colours as the second half. The nonrepetitive chromatic number of a graph \\(G\\) is the minimum integer \\(k\\) such that \\(G\\) has a nonrepetitive \\(k\\)-colouring. Whether planar graphs have bounded nonrepetitive chromatic number is one of the most important open problems in the field. Despite this, the best known upper bound is \\(O(\\sqrt{n})\\) for \\(n\\)-vertex planar graphs. We prove a \\(O(\\log n)\\) upper bound.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953438$7B749C48-055F-4193-A035-310355940068","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953438$0664178F-1632-4B6A-97A5-FE573732E203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953438$88A9C242-DC4C-4837-AD84-DDAF1907D63B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dca1ac040eabb6ff24c87da71cbb51264ace5a9a","datavalue":{"value":"6171890","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953438$886C5DC4-B9B7-4D24-85E2-0ADF187DF298","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af1a89f9587e041be1ef76d3b5410067b163905d","datavalue":{"value":"nonrepetitive graph colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953438$15D93B7E-69AB-44DF-B847-8E810F12B917","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":"Q1953438$130D6B2C-8DBD-426B-A933-C4BECB7EBD08","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"04d2086c02177306bdf1bba74b0cd8d45eca9132","datavalue":{"value":"bafkreibfm7a43aelkcgdqptymxltgaaxsrt27ta2ft4bcxd4hllh3bi624","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953438$6000A587-2D44-4A9B-B113-E9F3BE769587","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df2ac4302ab5bdc4b8bb4b86a1822386f779c47b","datavalue":{"value":{"entity-type":"item","numeric-id":5126756,"id":"Q5126756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d32bb5be7d170b5e5f494f8d39bdb9bfca436ea8","datavalue":{"value":{"amount":"+0.9077178239822388","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":"Q1953438$4CCCA224-49A5-40D6-B14A-467A7C7BB893","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a297a2f8329b06dde39cb02c12b90de10e9ef953","datavalue":{"value":{"entity-type":"item","numeric-id":3576675,"id":"Q3576675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e14542673fd39b8033bec03e9618f0586b3d3ab","datavalue":{"value":{"amount":"+0.8733159899711609","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":"Q1953438$846DB5AF-C301-4190-9159-793320EB1C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e71183a88fd2fdedac9732192a2193897ce87df8","datavalue":{"value":{"entity-type":"item","numeric-id":1010826,"id":"Q1010826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b18ece8b344afdee5217f1125e5d023d676028f","datavalue":{"value":{"amount":"+0.8656418919563293","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":"Q1953438$12A6C7EA-7975-4F8D-9730-2E02BB068863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38bb9ade2f84bab5e399a29238e10fe0af12d742","datavalue":{"value":{"entity-type":"item","numeric-id":941387,"id":"Q941387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72ff03a6e117b168b32cf3d50775038dcdb6be56","datavalue":{"value":{"amount":"+0.8558698296546936","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":"Q1953438$656AF6DC-5D2E-40DD-8067-E828B746C1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29a05078f1357e552b72a091ec453b069f685c21","datavalue":{"value":{"entity-type":"item","numeric-id":658062,"id":"Q658062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0cee4df354bc216bab97e380b8e2f401f9d8d31","datavalue":{"value":{"amount":"+0.8531183004379272","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":"Q1953438$4CD85A12-9355-4AEA-AB12-0277FFE59D8A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1953438","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1953438"}}}}}