{"entities":{"Q2741180":{"pageid":2751919,"ns":120,"title":"Item:Q2741180","lastrevid":47666629,"modified":"2026-01-02T09:22:06Z","type":"item","id":"Q2741180","labels":{"en":{"language":"en","value":"List colourings of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1642410"}},"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":"Q2741180$D9597E1B-368C-4910-B736-EEA1045485B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"765e7ee7763be297be5e64c6069685dd17d8ec3e","datavalue":{"value":"0979.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2741180$6284B252-D83A-487B-82BD-9A63585A5972","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63e1d7063ecd638677848b844accef77290c7ea4","datavalue":{"value":{"time":"+2002-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2741180$4B74DE10-9E8F-446E-9F85-E8BCD0D6A30D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2741180$1A286048-C36A-4613-9EA0-832EC82CAD2B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"65e4c471686b4752168d59b632831c20f548f8c3","datavalue":{"value":"1642410","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2741180$68AEC26D-5A91-49B6-AAD0-12709471A6E1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1b1b57278dbfe0191664931a2598a7540b5af04","datavalue":{"value":"lists","type":"string"},"datatype":"string"},"type":"statement","id":"Q2741180$4956508C-E13E-45CE-BDA7-163974E42A1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"568a80ce27cf206315133275c8b2f8046200abaa","datavalue":{"value":"colourings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2741180$E4F4D3CD-529F-4883-8FE8-D85F2B33962C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2741180$D7CC2E08-A760-4FC9-B6B2-356ED669B263","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f51628859d3741a7d4b3d92b1098364d202d37a4","datavalue":{"value":"choosability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2741180$DF28FBD6-7173-46A5-AF27-639AB03DA9A0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f7f1fcbb6559f616fb43cbccc2a4fe05892fcdc","datavalue":{"value":{"entity-type":"item","numeric-id":214988,"id":"Q214988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2741180$D6C0D94B-19D6-4770-BA0C-0FEE94EADE45","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":"Q2741180$2DF565D5-0020-43CF-B230-F01BCE04B5A9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3a07eb4ba22e588c159bfd706ee3f5084dfeca65","datavalue":{"value":{"text":"List colourings of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2741180$FBA6A018-8AB6-424A-944C-54587B9301A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1ce573eb201ffbfc3047186a86c85205068c8be9","datavalue":{"value":"A list colouring of a graph is a colouring in which each vertex \\(v\\) receives a colour from a prescribed list \\(L(v)\\). The list-chromatic number or choosability \\(\\text{ch}(G)\\) is the smallest \\(k\\) such that a graph always has a proper list colouring provided the prescribed lists are of size at least \\(k\\). If the lists are the same for each vertex, then \\(\\text{ch}(G)\\) reduces to the usual chromatic number \\(\\chi(G)\\). NEWLINENEWLINENEWLINEThis paper provides an excellent survey of list colourings. A section is devoted to results and conjectures regarding when \\(\\text{ch}(G) = \\chi (G)\\). Some time is spent on \\((a:b)\\)-choosability: each vertex gets a list of \\(a\\) colours, and we must choose \\(b\\) of these colours so that adjacent vertices receive disjoint sets. The author also examines \\(d\\)-defective colourings, where the subgraph induced by vertices receiving a fixed colour has maximum degree \\(d\\). List versions of Hadwidger's conjecture are given, except in this context one excludes \\(K_{r,s}\\) minors instead of \\(K_r\\) minors. Some new results are given regarding defective choosability of planar graphs. Another variation adds the restriction that adjacent vertices have a bound on the number of elements in common in their lists. The paper concludes with a review of different methods of proof for choosability results and examines the strengths and weaknesses of each. NEWLINENEWLINENEWLINEThe paper is excellently written. It is clearly organized and offers a variety of conjectures and open problems. This is a ``must read'' for anyone interested in colouring graphs.NEWLINENEWLINEFor the entire collection see [Zbl 0964.00035].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2741180$C12596FC-1418-4A98-BF6C-CE66EC0865B1","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":"Q2741180$117FC17F-2D2C-4C03-9542-A64A989E70FB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1dbd57450219921f7d7ad4afff02203dc91e3d4a","datavalue":{"value":{"entity-type":"item","numeric-id":2822593,"id":"Q2822593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"056c31b672d4fd5eca962745d0c679e0c6a2726c","datavalue":{"value":{"amount":"+0.8624423742294312","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":"Q2741180$79379C76-D976-410D-B91F-3B76F743083E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"079b51e971e1964e6a0dd3c56a915f7933006e2d","datavalue":{"value":{"entity-type":"item","numeric-id":687126,"id":"Q687126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec5abbfae1b5c4d85b693497bade6617ac1a68a2","datavalue":{"value":{"amount":"+0.8526008725166321","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":"Q2741180$B846A8E5-ED66-404F-A7C4-21004C9931B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15e7ff9740484e3231e248880e1fa9988062ffb2","datavalue":{"value":{"entity-type":"item","numeric-id":4210665,"id":"Q4210665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bb9f60d67444b00226a5b484904eaddc68b08f7","datavalue":{"value":{"amount":"+0.8468853235244751","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":"Q2741180$F6C09FCC-5EA6-4C5A-82A4-FB9240CE1318","rank":"normal"},{"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":"86f08df8d5dd7160f73b8159c4af5e6bb1a9e53c","datavalue":{"value":{"amount":"+0.8463258147239685","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":"Q2741180$7E46C5A7-8EDB-4BEA-90A3-DC2D78DCEFF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f715ae78af4315addc752c838269411425a7de5c","datavalue":{"value":{"entity-type":"item","numeric-id":4230860,"id":"Q4230860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1444f58d40e32a11ef82cc0c5358de24f0107357","datavalue":{"value":{"amount":"+0.8297549486160278","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":"Q2741180$B24C41C1-629E-418E-B8A6-B2739B039333","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2741180","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2741180"}}}}}