{"entities":{"Q687126":{"pageid":688975,"ns":120,"title":"Item:Q687126","lastrevid":47194528,"modified":"2025-12-31T23:32:28Z","type":"item","id":"Q687126","labels":{"en":{"language":"en","value":"List colourings of planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 429149"}},"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":"Q687126$9136AAEA-545A-4257-8CC4-569293397665","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c2209c6b65a59de313097cfa7754dc0840d21bdf","datavalue":{"value":{"text":"List colourings of planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q687126$6A72BB15-853D-41F2-A34C-A02A597CA008","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1666b22ca6eb297cf5b7468b87d057ed2fa63b5a","datavalue":{"value":"0790.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687126$F2BFDE36-AE0F-4925-ABB2-7B0A8B6D486D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4c88dd250da6328d9216d696691824e6acd65adb","datavalue":{"value":"10.1016/0012-365X(93)90579-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687126$325CEF84-8E16-4F24-BAEB-CCD1EC1CF373","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"31942340bee12a6dea1201818e993747a3803a5b","datavalue":{"value":{"entity-type":"item","numeric-id":442340,"id":"Q442340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687126$56B94570-B47E-40E5-8D09-98BFDADB0979","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":"Q687126$0CD502C1-F086-46AE-ACAE-898237BE381C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b6cd5815201d85bb68894181f8a778e0395c5390","datavalue":{"value":{"time":"+1994-06-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q687126$2E70874C-CBC8-4A01-A8DA-229B54A03127","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bb2c95bb38f141b77363338fbdd6dd083cc2ac2e","datavalue":{"value":"In an ordinary vertex colouring there is a set of \\(k\\) colours available, and a vertex colouring picks one of these colours for each vertex so that adjacent vertices receive distinct colours. In a list colouring there is a pre-assigned list of colours at each vertex, and in a colouring a vertex must receive a colour from its list. A graph is \\(k\\)-choosable if there is a proper list colouring for any assignment of lists with at least \\(k\\) colours available at each vertex. The choice number of a graph is the smallest \\(k\\) so that it is \\(k\\)-choosable.   In general, it is possible that a graph's choice number exceeds its chromatic number, in other words, the more general problem may be more difficult. However, the hope is that for special classes of graphs the choice number should be close to the chromatic number. Along these lines, two conjectures of Erd\u0151s, Rubin, and Taylor state that (1) there exists a planar graph which is not 4-choosable, and (2) any planar graph is 5- choosable. It is known that there are planar graphs which are not 3- choosable, and that every planar graph is 6-choosable.   The author presents a planar graph on 238 vertices which is not 4- choosable, therefore settling Conjecture (1) above. The second conjecture remains open.","type":"string"},"datatype":"string"},"type":"statement","id":"Q687126$4722A243-1180-4C8A-840F-36D09F9E0A71","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b687a818ec58a93e77f94a71ec71ff4e2750b160","datavalue":{"value":{"entity-type":"item","numeric-id":592090,"id":"Q592090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687126$223131B1-CFAA-4D50-B9FE-B1B5CAF70B1C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687126$0FA57A04-84A4-4E14-82F4-352F937C283D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687126$9C420C95-F507-42B3-8C32-43E485FE70B1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b2a79891bc03726f688e21cca8ff888ecd0cf49c","datavalue":{"value":"429149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687126$F31E97F2-2DAF-41EB-9CEA-02AE22F5F5BF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d7cda7b7bce8f5ee07c238e9cacb71a3a96be7d","datavalue":{"value":"list colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q687126$573DEF1B-4D49-4ED6-97D7-DDD42614A343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f27497f109320972d91be3badfd07688c13c0326","datavalue":{"value":"choice number","type":"string"},"datatype":"string"},"type":"statement","id":"Q687126$79A74ECF-FF78-474F-B8A9-85FD7E3797F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q687126$E80E83AE-61DC-4879-8CC8-BF661AFD5E8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q687126$A76DE440-37AD-4121-9E8A-8D44D1DDC037","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":"Q687126$85ECF750-00D9-4FB8-B51E-A0B13D82F7CB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"24fd97daa896675f87ac5a0d033eb933aea1b7c3","datavalue":{"value":{"entity-type":"item","numeric-id":3697034,"id":"Q3697034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687126$5CF72FEF-E6F0-4B82-AC44-AF9C5C99E512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdd0676f008d3d35603ace258b7c421e863d9a84","datavalue":{"value":{"entity-type":"item","numeric-id":1196681,"id":"Q1196681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687126$5BEB8E0C-6F8F-4986-9594-B2D848286C5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3573b87026595a32002fa2dc54ac8b096bc29f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3922703,"id":"Q3922703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687126$75407578-0878-4A70-A8B7-F2467EE82465","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687126$427EAF35-AD11-4F52-B6F0-49346AAF43F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b048e550daccef3ab3d36df1ef2635b07519043","datavalue":{"value":{"entity-type":"item","numeric-id":1309815,"id":"Q1309815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687126$99E0E756-9A78-429A-9DD8-B46CBB94D09C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ebf421577b16a158a52d3a6828f6fc1f83300d17","datavalue":{"value":"https://doi.org/10.1016/0012-365x(93)90579-i","type":"string"},"datatype":"url"},"type":"statement","id":"Q687126$449DD485-EA9F-4504-95D7-2CC5539FC41D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9d9b7aa7a69490016e9705a8a5b74320cf92eb69","datavalue":{"value":"W4212970601","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687126$CF8F9AB6-748C-4F66-9798-B4D9D816B9AA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"425dc63e069da791b80bfcb87acf16ed6b48f86d","datavalue":{"value":{"entity-type":"item","numeric-id":2498006,"id":"Q2498006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"199b6fb47c02754576bfb53e68b98d47166208fc","datavalue":{"value":{"amount":"+0.9382280707359314","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":"Q687126$851D6558-1ED7-4CD4-A2BB-CDB9EC0E70D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97f6099719ce848d55073fc0593b9d0c37fe322e","datavalue":{"value":{"entity-type":"item","numeric-id":1916256,"id":"Q1916256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9103124a053f01b622ba328d48a577d14138502","datavalue":{"value":{"amount":"+0.8892247080802917","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":"Q687126$9892ECB8-8521-4412-8AEB-C39F872ECBAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da7842ce1cb86a48361839e710bbc55aeed7d972","datavalue":{"value":{"entity-type":"item","numeric-id":1333334,"id":"Q1333334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09de1ba04f425c3cf40260759e6bd11fd4d01417","datavalue":{"value":{"amount":"+0.8884161114692688","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":"Q687126$87D2E27D-23F8-4C4E-B0A5-C48C65F195D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4911da53e720622bbd6f2baa840545f9570a599","datavalue":{"value":{"entity-type":"item","numeric-id":345127,"id":"Q345127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fba7238cba30867c1fbb0776f2af4c2605f9449","datavalue":{"value":{"amount":"+0.8842519521713257","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":"Q687126$13729A33-FCBD-4B25-B0F4-ACABF5C69930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db0c5eeefdf61c24fe9fa36189b8dda1db3e4882","datavalue":{"value":{"entity-type":"item","numeric-id":4882549,"id":"Q4882549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7b86f8f527d0099c1c3aca61546cd43bd407119","datavalue":{"value":{"amount":"+0.8674613833427429","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":"Q687126$DC9C54A5-0729-4B07-8AEE-22AF728C4C06","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:687126","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:687126"}}}}}