{"entities":{"Q2757076":{"pageid":2767815,"ns":120,"title":"Item:Q2757076","lastrevid":83108426,"modified":"2026-05-07T06:05:31Z","type":"item","id":"Q2757076","labels":{"en":{"language":"en","value":"A note on vertex list colouring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1675773"}},"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":"Q2757076$C35A2A5B-62A2-4DD2-8D9B-79502384DE82","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f83421c98ca63ab24d8fac13243742407127ee5","datavalue":{"value":"0986.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2757076$74374F84-1624-4F62-BF40-08AD15DF251E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9a20f0d004802158483b0a08a5d07db39cbed99d","datavalue":{"value":"10.1017/S0963548301004758","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2757076$78D4F5DF-2EA5-4045-ADAE-5CE46A62D96D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef9f22506a0bcbf1151d6523fea2bf6c3ee4e900","datavalue":{"value":{"entity-type":"item","numeric-id":353398,"id":"Q353398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2757076$F66AA79F-2BAB-4FA6-9D7C-B3C6EDFF88D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc98aa839a361f8a72b00376d60e99225cffa57","datavalue":{"value":{"entity-type":"item","numeric-id":2703019,"id":"Q2703019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2757076$A5B792C7-F3C7-4598-B875-CC50DF13ACAA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"89979698039692d8b30dd476805176a82a96347c","datavalue":{"value":{"time":"+2002-06-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2757076$92746C4C-8986-4100-B590-9BB5125A4C97","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2757076$757A5CF1-0EC8-4983-9982-462F4470DAAA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f47e854b6852ecf7c2988e7157785de72f5c8157","datavalue":{"value":"1675773","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2757076$9889F680-1765-497A-AF51-6901317C7ACE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10faeff6c6463e170c9b35d2fd1c8a70dfa870ae","datavalue":{"value":"list-colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2757076$D9B8B532-35C8-43ED-AA50-83E1718F85C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52d051d1eb56c52e25dc7df49b5f8b3ed6acad4a","datavalue":{"value":"colour","type":"string"},"datatype":"string"},"type":"statement","id":"Q2757076$330783E9-0FF9-4ED3-9339-A76C2ABDC530","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":"Q2757076$6CC3A605-D601-4F86-B53A-DFDE37D5ADE3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f7edf4b5a28f71e8811af50df2d58b9d54b8885","datavalue":{"value":"https://doi.org/10.1017/s0963548301004758","type":"string"},"datatype":"url"},"type":"statement","id":"Q2757076$2B06CF6A-C12F-4069-AA41-482115436985","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ed6189e026c49b7fe0b9070de5e7b83850365d2f","datavalue":{"value":"W2119305988","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2757076$8558F5C1-BE64-47FB-B6AD-F1D475D36FFD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"148b482878b75fb5f2d3690a17e5db9ca88da06f","datavalue":{"value":{"text":"A note on vertex list colouring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2757076$1593D49B-CE5E-49B2-9C12-6AAD008F9260","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"92de6a462e5eef731a2bb14e6e7031d1fe0fec2e","datavalue":{"value":"Suppose that we are given a graph \\(G\\), and for each vertex \\(v\\) of \\(G\\) we are given a list set \\(S(v)\\) of \\(k\\) colours. A list-colouring is a selection of a colour from \\(S(v)\\) for each vertex \\(v\\) such that adjacent vertices receive distinct colours. \\textit{B. Reed} [The list colouring constants, J. Graph Theory 31, No. 2, 149-153 (1999; Zbl 0926.05019)] conjectured that a list-colouring always existed provided that for each vertex \\(v\\) and each colour \\(c\\), the number of neighbours of \\(v\\) that have colour \\(c\\) in their lists is at most \\(k-1\\). In this paper the author proves a weak version of Reed's conjecture; namely the case that \\(k\\) is even and the number of neighbours of \\(v\\) that have colour \\(c\\) in their lists is at most \\(k/2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2757076$AF693753-C3F8-4909-9798-189CF0B2FA87","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":"Q2757076$CFC47275-D55E-4DAF-8640-8218E211486D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4da60240f6f4e5ef9274f2d7649afc5a3feaff2","datavalue":{"value":{"entity-type":"item","numeric-id":4798107,"id":"Q4798107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f71421d89541fc76473499ff682039aed0178320","datavalue":{"value":{"amount":"+0.868668794631958","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":"Q2757076$34F3A7B1-8336-4CE4-A948-6E1CE4ED310E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"224373ee3ad0c5b393b59972e98172f048fcebe3","datavalue":{"value":{"entity-type":"item","numeric-id":4329136,"id":"Q4329136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f71421d89541fc76473499ff682039aed0178320","datavalue":{"value":{"amount":"+0.868668794631958","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":"Q2757076$7AA364FB-3ADA-409E-B3B8-4712615203CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ece2f7e048a459619a3ab956f69597dd97d25dd","datavalue":{"value":{"entity-type":"item","numeric-id":1689939,"id":"Q1689939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"582814cc5fd7c30901db787e3d71eeff4b66c695","datavalue":{"value":{"amount":"+0.8113303780555725","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":"Q2757076$2F25954A-40CA-43F0-ABD8-9F40AEE11185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e296962f909bb56abd001b0c6a0c1131b0904f0","datavalue":{"value":{"entity-type":"item","numeric-id":1850621,"id":"Q1850621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c752e2d5e3a0f2b7b4e01eb216cff66796a0f47","datavalue":{"value":{"amount":"+0.8007954359054565","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":"Q2757076$2D07B060-2FA9-41E5-B5FF-720F70B8D8B2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on vertex list colouring","badges":[]}}}}}