{"entities":{"Q491533":{"pageid":493300,"ns":120,"title":"Item:Q491533","lastrevid":56984406,"modified":"2026-03-25T11:39:08Z","type":"item","id":"Q491533","labels":{"en":{"language":"en","value":"On-line list colouring of random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6475715"}},"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":"Q491533$7B8697C5-8AE0-437B-96B1-B2467CBAA967","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8360449b97a3f5cd4fc2407fe3d74c83665da3aa","datavalue":{"value":{"text":"On-line list colouring of random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q491533$B627C7E0-058B-4335-A105-7881C57726EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9474a26b43233ae6e6efb759d8d000360d3e05a1","datavalue":{"value":"1327.05109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q491533$C15CA1DD-EDB6-4342-BBED-478B34B1D1E6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1bd2ccad443c7abc989928f6e000b315d9b1786e","datavalue":{"value":{"entity-type":"item","numeric-id":268259,"id":"Q268259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$325A04E8-42B7-41CB-A16B-F7C11DCC82ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac2c2a227d28a236f9023d4aef4cfb5c991709ef","datavalue":{"value":{"entity-type":"item","numeric-id":281603,"id":"Q281603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$7C209717-3A68-46D1-9461-860A6870C0C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6197eba997efc9b4d1afb25ce947d80519065cc","datavalue":{"value":{"entity-type":"item","numeric-id":265089,"id":"Q265089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$D3F01433-44AA-4C43-9884-DE579EA9A435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$850F2B03-19FF-499B-9AFC-B475D4A18759","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":"Q491533$FD9E1E0C-1168-48E3-BFDC-82A2B24B9DD6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ddf6ecb9e5ed20bb1adfdb1d89c4230618bbee22","datavalue":{"value":{"time":"+2015-08-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":"Q491533$60A3DD01-952E-44A2-8CFA-CA10126CAEEA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6dcbda58d006330fbbee3234c26a0fbeba7f7007","datavalue":{"value":"https://arxiv.org/abs/1501.07469","type":"string"},"datatype":"url"},"type":"statement","id":"Q491533$2142656B-C1F0-44ED-BAD6-B05B8661EBD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ef7213f5a94a7cdcfcfd48d6351d4226a465a615","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p41","type":"string"},"datatype":"url"},"type":"statement","id":"Q491533$E4E70FD7-76ED-4D79-9C59-6D309DCFDF1C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"587d8907a57177eace1cc8c803ddfba7d8373cd3","datavalue":{"value":"Summary: In this paper, the on-line list colouring of binomial random graphs \\(\\mathcal{G}(n,p)\\) is studied. We show that the on-line choice number of \\(\\mathcal{G}(n,p)\\) is asymptotically almost surely asymptotic to the chromatic number of \\(\\mathcal{G}(n,p)\\), provided that the average degree \\(d=p(n-1)\\) tends to infinity faster than \\((\\log \\log n)^{1/3} (\\log n)^2 n^{2/3}\\). For sparser graphs, we are slightly less successful; we show that if \\(d \\geq (\\log n)^{2+\\epsilon}\\) for some \\(\\epsilon>0\\), then the on-line choice number is larger than the chromatic number by at most a multiplicative factor of \\(C\\), where \\(C \\in [2,4]\\), depending on the range of \\(d\\). Also, for \\(d=O(1)\\), the on-line choice number is by at most a multiplicative constant factor larger than the chromatic number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q491533$B1BD08EB-23D6-42C8-9CF6-E2D5680307B2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q491533$451F8D19-53BF-49EE-970F-7656ED9A9824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q491533$59C8FDD8-3BC8-43A8-A135-3D93129FCEC7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c157b6d90a621fb97177935950fb804c9c69e5ee","datavalue":{"value":"6475715","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q491533$D0454845-787C-4397-B5F4-774EF34CAB9F","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":"Q491533$DC10EBE6-68F9-46EB-8AC3-7B6EA7A36221","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed7ec6f0e6329fc3509021e1635ba44b02e95ce5","datavalue":{"value":{"entity-type":"item","numeric-id":4291205,"id":"Q4291205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$D8CEB415-7753-4EC3-B420-1B08CB00C861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f80aadf78dae9fc5a0138327cacf9a09e7cfa15","datavalue":{"value":{"entity-type":"item","numeric-id":3142409,"id":"Q3142409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$B51765EE-5DDF-4D6F-8E87-FABB703A8388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3d7dd2ca8337438961814aff0c1870761263723","datavalue":{"value":{"entity-type":"item","numeric-id":1977428,"id":"Q1977428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$37D92F15-0162-477A-9531-72FB83096AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6c6e30e71ec4191c814859d4ee8748fe67c73bf","datavalue":{"value":{"entity-type":"item","numeric-id":5903892,"id":"Q5903892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$60702280-47B0-4982-85EB-2D951B535D97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e223601faca9d55159622a8249ba08f0bc3839c","datavalue":{"value":{"entity-type":"item","numeric-id":4736774,"id":"Q4736774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$2F3D3B11-6EFC-4F38-98E7-EFD49D799E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$1B0EBD4F-7557-4B18-BCEE-736B18B95BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"691f4aa6148c8dc3f0dacd89dcf3f2e39ed84a8b","datavalue":{"value":{"entity-type":"item","numeric-id":4948043,"id":"Q4948043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$2B0EE3FB-1190-47A6-A055-C82E3ADF4602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9411b1b66a37576bbed5be13161ebdeb6fca17fb","datavalue":{"value":{"entity-type":"item","numeric-id":4798177,"id":"Q4798177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$F4EB70BB-1713-42CF-A541-1784D620A05E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9ea8d8c4b769406643d68a9b4e32d679afc9972","datavalue":{"value":{"entity-type":"item","numeric-id":1598877,"id":"Q1598877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$C22EA970-C1BD-4AC0-943B-7089B22F63CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33a92aa47e012f6181090458caf043391a7b6ec9","datavalue":{"value":{"entity-type":"item","numeric-id":1850565,"id":"Q1850565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$7D5B11C6-0BFF-423F-8FB8-0B4F1B9381F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdd51985f8df50c8dac6708d27413a9259a40295","datavalue":{"value":{"entity-type":"item","numeric-id":5905438,"id":"Q5905438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$B5E28ECA-3524-48CF-8C6C-A906950D15DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cf05a693fc5823281f069264773fe3cde45b742","datavalue":{"value":{"entity-type":"item","numeric-id":5966556,"id":"Q5966556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$7460DC9D-5332-4E2A-AF6C-9D4DF9212B99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bcf2b4c2b6c7326a3acf6bf57028e463e8c28e","datavalue":{"value":{"entity-type":"item","numeric-id":2380232,"id":"Q2380232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$625C3B06-65F8-4D0D-82F5-031473EC4245","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fad64547aa8c484ae73fda6b3bc2f85436a1625d","datavalue":{"value":{"entity-type":"item","numeric-id":1052343,"id":"Q1052343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$B97EBA47-5657-483B-A7C5-82CDB0BB117A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a06ecc9798c878486ed34156f82966ff02a2eb6","datavalue":{"value":{"entity-type":"item","numeric-id":4256092,"id":"Q4256092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$ED78273F-E3A3-485F-B4EF-9E0ACD4CCA77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92077b84d7a6aabab7f2ca3e178b3e89c72e8c83","datavalue":{"value":{"entity-type":"item","numeric-id":2380291,"id":"Q2380291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q491533$59AD8781-CD55-48C0-9973-57DD394C3376","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"e7a8190e538ccc4104500d7027e3bf7ca760a0f9","datavalue":{"value":"bafkreifzir7fwhop4gdnah2kaq2fggm4shqjfvpwtvtq7ehzxgnshn4omq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q491533$7F236400-C0A6-4DE7-AA6E-01BDFB95DCC1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27ae25bdd59016252ca3ba75b56cb31e6d9dfa0a","datavalue":{"value":{"entity-type":"item","numeric-id":2380291,"id":"Q2380291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da55682f704138911717ddb9fdc7bec5317cf8af","datavalue":{"value":{"amount":"+0.8741146326065063","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":"Q491533$67DB83E0-0DD0-4339-938E-A1B8FBA79D2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcc6864c57725cd9ab9f6f274746d64eb87b5b42","datavalue":{"value":{"entity-type":"item","numeric-id":1977428,"id":"Q1977428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb0c0959e2d22f1eae5b5abac5b2a767660392cf","datavalue":{"value":{"amount":"+0.8402607440948486","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":"Q491533$C8C995FC-4581-4695-B86F-4D79BF3B4F13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f3fb74a708979cc1f503bf7f09a1936b1ccf54f","datavalue":{"value":{"entity-type":"item","numeric-id":5365033,"id":"Q5365033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d7208ced8cfc7e8b2dfe9a445136dbedf29d753","datavalue":{"value":{"amount":"+0.8314926624298096","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":"Q491533$BD4E9193-4706-422A-93F5-722129C93736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd4da08196384e5fe6bde6f548d9f7ffb80b97ed","datavalue":{"value":{"entity-type":"item","numeric-id":4015271,"id":"Q4015271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c865d89e865cef30dc5582535d400753b9f27279","datavalue":{"value":{"amount":"+0.831020176410675","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":"Q491533$362EEB61-D4BF-4ACE-AEB1-89AF0202D910","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cca6ded64f5d7acc059b4e03d6902b5c27adfba","datavalue":{"value":{"entity-type":"item","numeric-id":4601441,"id":"Q4601441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0af0764d9e26cc445eb6b211dd85bf2bec7d877","datavalue":{"value":{"amount":"+0.8297984600067139","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":"Q491533$49CF78CF-3A26-473F-B906-D5564B400DED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:491533","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:491533"}}}}}