{"entities":{"Q2380291":{"pageid":2391034,"ns":120,"title":"Item:Q2380291","lastrevid":72652830,"modified":"2026-04-14T06:19:16Z","type":"item","id":"Q2380291","labels":{"en":{"language":"en","value":"On-line list colouring of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5686830"}},"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":"Q2380291$8940580F-AE8C-44F7-B3EB-A20E6FE8EC8D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1b9acdae66696550b12eac1f7ca987a91c07e278","datavalue":{"value":{"text":"On-line list colouring of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2380291$6C6DB5AB-89C1-485E-A6A5-0E0403293390","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0af7515e8f9faae094a820f079daa6b4509f6610","datavalue":{"value":"1186.05061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380291$8D4466D1-7333-48C2-8F4E-ED0175ED0103","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":"Q2380291$ECBC8B53-574D-4A71-BD6A-C6375FC5FB1E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"143e8774a45e663375c24b3b343519cf2933b18c","datavalue":{"value":{"time":"+2010-03-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":"Q2380291$8EE5EDE2-9352-4E92-83D3-7E1270220CAB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cabfe1b367c9f1de0d7317977d3af11e303f207f","datavalue":{"value":"https://eudml.org/doc/227366","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380291$8D023C93-E938-467C-96DD-0C4FD2D99A53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"5db19614a48a89302d1d2bb856fdd85e8cbdf202","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r127.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380291$198BE550-3473-4F98-B5BF-23A77610634C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b1971c08cb0f4a184adb47f94ef4d809966db440","datavalue":{"value":"Summary: This paper studies on-line list colouring of graphs. It is proved that the on-line choice number of a graph \\(G\\) on \\(n\\) vertices is at most \\(\\chi(G)\\ln n+1\\), and the on-line \\(b\\)-choice number of \\(G\\) is at most \\(\\frac{e_\\chi(G)-1}{e-1}(b-1+\\ln n)+b\\). Suppose \\(G\\) is a graph with a given \\(\\chi(G)\\)-colouring of \\(G\\). Then for any \\((\\chi(G)\\ln n+1)\\)-assignment \\(L\\) of \\(G\\), we give a polynomial time algorithm which constructs an \\(L\\)-colouring of \\(G\\). For any \\((\\frac{e_\\chi(G)-1} {e-1}(b-1+\\ln n)+b\\)-assignment \\(L\\) of \\(G\\), we give a polynomial time algorithm which constructs an \\((L,b)\\)-colouring of \\(G\\). We then characterize all on-line 2-choosable graphs. It is also proved that a complete bipartite graph of the form \\(K_{3,q}\\) is on-line 3-choosable if and only if it is 3-choosable, but there are graphs of the form \\(K_{6,q}\\) which are 3-choosable but not on-line 3-choosable. Some open questions concerning on-line list colouring are posed in the last section.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380291$F5F4A82E-1666-4161-A3F8-545825D17F63","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380291$BE755201-6196-4B78-87CB-5BA701D6DAFB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e895b22e46727d46ff7c6c3dc14daeb87badae1e","datavalue":{"value":"5686830","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380291$F50C51D7-8F25-4305-BD2C-8B1B56282DA6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6b19b09c7519f38384d021f845694abb1cfab04","datavalue":{"value":{"entity-type":"item","numeric-id":168189,"id":"Q168189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380291$B1CCE8E2-6F1B-4662-9B33-C19A6DA816B3","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":"Q2380291$50ACAB14-D676-48CF-A19F-5ED373900FA6","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"4d81e122acb689f6b9e94928cdf8200ca1bdf3c5","datavalue":{"value":"bafkreifhjqcz7pu6b56rek63trmmmqvlired2cmuronzfbq5qfc4p3grie","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380291$0E895241-AA4F-45C5-A65D-0AD04730FE56","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e151f41a80a8e65f1fb2b630b598f754809ce35","datavalue":{"value":{"entity-type":"item","numeric-id":491533,"id":"Q491533"},"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":"Q2380291$149AF99E-94BB-4F13-811A-29BFED2805D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"389dbe182a01b53d2b350aa1c10655aec070743a","datavalue":{"value":{"entity-type":"item","numeric-id":2441619,"id":"Q2441619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06defca0868e9e7b2db663a886b8dee4365d65ce","datavalue":{"value":{"amount":"+0.8640989661216736","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":"Q2380291$DC3D6D41-2807-4775-B551-F775340FE907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa4c0ec4c721b2cd131ed141a9f6b01635c3794a","datavalue":{"value":{"entity-type":"item","numeric-id":2657183,"id":"Q2657183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4795e2d7409624df45507002875ac09678f77a28","datavalue":{"value":{"amount":"+0.8595920205116272","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":"Q2380291$4BB1CEBF-710E-4A00-9401-85F9CEC51D72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e24ce59e5e3c78e21325619a845aba375ece974c","datavalue":{"value":{"entity-type":"item","numeric-id":2862550,"id":"Q2862550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5625f051d4536d6abeaa8065fc159ef8ee70c1e0","datavalue":{"value":{"amount":"+0.854491114616394","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":"Q2380291$EBC3B74E-1D79-4683-B4B1-DBEF2189534C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6791e35c160e3278e09e9f6ebb1bcdb315b9fc2a","datavalue":{"value":{"entity-type":"item","numeric-id":1264277,"id":"Q1264277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6da885ec04b37347ecc9ed34844388f58af55baf","datavalue":{"value":{"amount":"+0.853229284286499","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":"Q2380291$D6594EB1-CC98-4E37-8AB7-CD1B9B1DDD9A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On-line list colouring of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On-line_list_colouring_of_graphs"}}}}}