{"entities":{"Q2497995":{"pageid":2508738,"ns":120,"title":"Item:Q2497995","lastrevid":49887259,"modified":"2026-01-11T15:51:04Z","type":"item","id":"Q2497995","labels":{"en":{"language":"en","value":"Set colourings of graphs. (Reprint)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5044122"}},"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":"Q2497995$D7C1DD41-862C-4517-8F21-39209D1FB422","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d39c9dc09cd6b3311a4402d501d51f9fef03231f","datavalue":{"value":{"text":"Set colourings of graphs. (Reprint)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2497995$D30AC845-873A-4361-ABFB-0B900FB3F0C2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2e6fb31180bfc1296d6a865ef0cab6c6aeea565","datavalue":{"value":"1098.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497995$FE46E816-1900-46F3-9C3B-06366308705B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a14bac90927db699ac4af297f1d406f2762c11d","datavalue":{"value":{"entity-type":"item","numeric-id":168581,"id":"Q168581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497995$96B664CC-E83D-41DA-830B-E0F107964344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bde2140b5b5ce5800790e0742b7d8b3fabb665a6","datavalue":{"value":{"entity-type":"item","numeric-id":1253258,"id":"Q1253258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497995$500097F4-D95D-4AA8-B3D1-02F6B87592DE","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":"Q2497995$DBEC536B-DD34-4F4A-B2EF-3DD0FBD34E60","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fb876cd0509c83d752b9ca15b7a238c782dbf5de","datavalue":{"value":{"time":"+2006-08-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2497995$A100E46B-7B9A-4975-9F2F-F8FA315C78B8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ac173757a3c2abf220a6606de09284c7b366625","datavalue":{"value":"This article is a reprint of an important paper published in Discrete Math. 25, 21--26 (1979; Zbl 0403.05038).   An \\(r\\)-set colouring of a graph \\(G\\) is an assignment of \\(r\\) distinct colours to each vertex of \\(G\\) so that the sets of colours assigned to adjacent vertices are disjoint. We denote by \\(\\chi^{(r)} (G)\\) the minimum number of colours required to \\(r\\)-set colour \\(G\\). The set-chromatic number of \\(G\\), denoted by \\(\\chi^*(G)\\), is defined by \\(\\chi^* (G) = \\inf_r \\chi^{(r)} (G) / r\\). Clearly \\( 2 \\leq \\chi^* (G) \\leq \\chi (G)\\).  By making use of a recent result of L. Lov\u00e1sz we prove that \\(\\min \\{ \\chi^{(r)} (G) \\;:\\;\\chi(G) = k \\} = 2r + k - 2\\) and \\(\\min \\{ \\chi^{(r)} (G) \\;:\\;G\\) is uniquely \\(k\\)-colourable\\(\\} = 2r + k - 1\\). In particular, given any \\(k\\), \\(\\chi^*(G)\\) may be arbitrarily close to 2, and given any \\(r\\), the ratio \\(\\chi^{(r)}(G)/\\chi(G)\\) may be arbitrarily close to 1, even if \\(G\\) is uniquely colourable. The results disprove a conjecture of D.P. Geller.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497995$C8F399B0-059B-48FF-AAB8-12227C5F4E5A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497995$2479945D-F6EB-4B2A-B880-E2E67184B655","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bb5692eecd3ff8ebe1193a38a11199f821218fb0","datavalue":{"value":"5044122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497995$9FB87986-8F6F-46B1-91B5-006CB217DE28","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8eb084c437ac827e887838618fca3b4e64a4d3a","datavalue":{"value":"set colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497995$BEF5C528-AB3F-4A3B-B343-BE43C9555B70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4851331e6cc66373fb01766485cfd2499cf0f17c","datavalue":{"value":"set-chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497995$1D6D3FBA-42CC-4E14-BE03-B4D512CA4FFE","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":"Q2497995$17A5B55E-F681-4A1B-949E-72A7CFEC817C","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":"Q2497995$FBB4B437-A012-4039-9193-54E6A889C972","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cbd76388f60c356d2cde39bdf63fee80f2244311","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.03.016","type":"string"},"datatype":"url"},"type":"statement","id":"Q2497995$5FCD02A0-55BB-4973-A2C5-245E628163D2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"45b8183d9813e3e010e133d6cee1ad7f6eace815","datavalue":{"value":"W2037296716","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497995$B7EB53BE-2076-4E3C-8066-9650711965D0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497995$E7FE8D3E-BB73-4628-8473-49F42B2761E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82bd142382c48198bd3d062596f9da54dc955038","datavalue":{"value":{"entity-type":"item","numeric-id":1230631,"id":"Q1230631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497995$7775A582-0A57-412B-BA76-A578F48018B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4120bafbef102d43a78cc532543a307c4f4aba37","datavalue":{"value":{"entity-type":"item","numeric-id":1843453,"id":"Q1843453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497995$5B0CDCB4-9528-4729-9307-EF581AE7A228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc55d015d600bc4e992a5aceef27254fa995d9a","datavalue":{"value":{"entity-type":"item","numeric-id":4046069,"id":"Q4046069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497995$6227F47C-79D7-462C-9D3F-D472D54483EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e4db718337c47f930eac480f7f0beee5c7871d7","datavalue":{"value":{"entity-type":"item","numeric-id":5554997,"id":"Q5554997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497995$8B6EF476-B869-4D78-94DF-1014ACF07BC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a19db9ac81b41bda4141d0a8537b5930e583d51","datavalue":{"value":{"entity-type":"item","numeric-id":4405185,"id":"Q4405185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497995$F54AD378-77E3-42BB-B5A6-BBE1E5815832","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"47fcd3b94ba03cd2407d7c444b247c1c95359ba1","datavalue":{"value":"10.1016/J.DISC.2006.03.016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497995$11F6C8AA-6419-4128-BAB6-25FA68E211AD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7eb177e54c5106fb0912aeafe71eb58132e34c60","datavalue":{"value":{"entity-type":"item","numeric-id":3011613,"id":"Q3011613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4df6e34f657ab4a25fc247af38dc6946271b7b4c","datavalue":{"value":{"amount":"+0.8012225031852722","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":"Q2497995$2E828953-368D-454C-9FDB-C022FED063C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b0056495ac40ff6890aca5dbfd669963f9da5c8","datavalue":{"value":{"entity-type":"item","numeric-id":3560781,"id":"Q3560781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d46893514a9dec67a25a3621b59d674e227efbc","datavalue":{"value":{"amount":"+0.7981765866279602","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":"Q2497995$2EFE2553-6D78-4449-B503-AC70D29ECC0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24e2ec28ba077e49cd14c4b13dd41f944b1841ce","datavalue":{"value":{"entity-type":"item","numeric-id":3699709,"id":"Q3699709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a7a43402821acc6d2b41465096c3af458b3f23a","datavalue":{"value":{"amount":"+0.7957932353019714","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":"Q2497995$24EA8AAC-B9E0-4C80-847E-014D1610618C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"091340984cfad6f66d1a0806e383b1ed2dc7e638","datavalue":{"value":{"entity-type":"item","numeric-id":5492615,"id":"Q5492615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85393a57c6b9d3ed0fd491f0721897816f550442","datavalue":{"value":{"amount":"+0.791928768157959","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":"Q2497995$113FDD84-86AD-4E81-830F-D6C6ED5D3C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5d8bacf5fde4ee5d9c53339d89ebce5a8b0ebba","datavalue":{"value":{"entity-type":"item","numeric-id":4351066,"id":"Q4351066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e6ae98e942e2edc767642e1e6d6919ba04fa919","datavalue":{"value":{"amount":"+0.7881944179534912","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":"Q2497995$BB722924-3751-45CF-ACFA-626DA8267347","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2497995","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2497995"}}}}}