{"entities":{"Q2032707":{"pageid":2043449,"ns":120,"title":"Item:Q2032707","lastrevid":54019667,"modified":"2026-01-26T02:47:01Z","type":"item","id":"Q2032707","labels":{"en":{"language":"en","value":"Comparison of sum choice number with chromatic sum"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7358314"}},"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":"Q2032707$CB99EC80-6B44-4013-91C2-F6F4F353B87A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d68f11f303cf177a8eeda5e81f438de8c7ca64e6","datavalue":{"value":{"text":"Comparison of sum choice number with chromatic sum","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2032707$8F7CF15F-A489-41A7-8ED2-7FC64AD76EDF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e5763380370f80217a2341c5c35d3ef80aa1090a","datavalue":{"value":"1475.05070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2032707$048A0F87-D145-4A44-99C6-D4581B161ED3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4a5db7ef6b3b725bf435808a6ed1b79c1c0e8ce","datavalue":{"value":{"entity-type":"item","numeric-id":186138,"id":"Q186138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$91078B4A-BD95-462B-9C66-22E2365D7F71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5d0dd44f11aa3b767a2bb67055164f3a221a7dbe","datavalue":{"value":{"entity-type":"item","numeric-id":186139,"id":"Q186139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$82C0D7B8-A7D1-435E-AE16-39E76892CF06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$E928F805-6A18-4091-AA99-1A5C98A58C41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"31942340bee12a6dea1201818e993747a3803a5b","datavalue":{"value":{"entity-type":"item","numeric-id":442340,"id":"Q442340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$390DE9B8-A772-4A0B-B962-BBC7A867D465","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":"Q2032707$3A56BC07-5A17-4609-A87B-87CE41386648","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9e3cc057fc0f295f9082b73bf1f37a9692cb13f4","datavalue":{"value":{"time":"+2021-06-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2032707$99A21918-129B-4019-8554-8606654BEC13","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"757bfc7da79dfc707b3371cae768586f89214253","datavalue":{"value":"For a simple graph \\(G = (V(G),E(G))\\), with both \\(V(G)\\) and \\(E(G)\\) finite sets, a proper coloring of \\(G\\) is here a map \\(\\phi : V(G) \\rightarrow \\{1,2,3,\\ldots\\} = \\mathbb{N}\\) such that every pair of adjacent vertices receive distinct colors. The chromatic sum \\(\\Sigma(G)\\) of \\(G\\) is the minimum of the sum of colors of the vertices \\(\\sum_{u\\in V(G)}\\phi(u)\\) among all proper colorings \\(\\phi\\) of \\(G\\). Suppose we have a list/set \\(L(u)\\) of available colors for every vertex \\(u\\in V(G)\\). The graph \\(G\\) is \\(L\\)-colorable if there is a proper coloring \\(\\phi\\) of \\(G\\) with \\(\\phi(u)\\in L(u)\\subseteq \\mathbb{N}\\) for each \\(u\\in V(G)\\). A function \\(f : V(G) \\rightarrow \\mathbb{N}\\) is a choice function of \\(G\\) if \\(G\\) is \\(L\\)-colorable for every list assignment \\(L\\) with \\(|L(u)| = f(u)\\) for each \\(u\\in V(G)\\). For a choice function \\(f\\) let \\(\\operatorname{size}(f) = \\sum_{u\\in V(G)}f(u)\\) and define the sum choice number \\(\\chi_{sc}(G)\\) as the minimum of \\(\\operatorname{size}(f)\\) among all choice functions \\(f\\) of \\(G\\).  This article investigates two functions \\[ g(n) := \\max_{\\Sigma(G) = n}\\frac{\\chi_{sc}(G)}{\\Sigma(G)} \\text{ and } h(n) := \\max_{|V(G)|= n}\\frac{\\chi_{sc}(G)}{\\Sigma(G)}. \\] By definition one has that \\(\\Sigma(G)\\leq \\chi_{sc}(G)\\) and a greedy coloring shows that \\(\\chi_{sc}(G) \\leq |V(G)| + |E(G)| := \\mathrm{GB}(G)\\), the greedy bound of \\(G\\). This article derives some upper and lower bounds for the functions \\(g\\) and \\(h\\) as well as some exact values of both \\(\\Sigma(G)\\) and \\(\\chi_{sc}(G)\\) for some specific known graphs \\(G\\), like the complete, cycle and star graphs. The partial results presented support the conjectures that both \\(g\\) and \\(h\\) are \\(\\Theta(\\log(n))\\)-functions for large \\(n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2032707$6EF51B47-56E6-4E86-A14A-8976C0D62A86","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"40a8c8304e09a825de719366905817f3f4c840d6","datavalue":{"value":{"entity-type":"item","numeric-id":368450,"id":"Q368450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$3B25BF6A-AECD-4F6B-B445-92CD33497CB2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2032707$3DC0DF8E-3ADF-4C93-AF55-5597DFDB42D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"89678960dc4ddea6dbb598d851581405d3a0890b","datavalue":{"value":"7358314","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2032707$FF3DFE9B-4C67-4AE1-B016-CA4805FEC0E6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2032707$9060ED8C-0056-4F15-8F09-64D4B3F4D518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15b66a6079b846629b0c8e49fc4dd12461f6a73e","datavalue":{"value":"chromatic sum","type":"string"},"datatype":"string"},"type":"statement","id":"Q2032707$09D19797-87A0-418C-88C7-A5665ADC9FDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f27497f109320972d91be3badfd07688c13c0326","datavalue":{"value":"choice number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2032707$0660CE79-71EA-4153-9058-21199DDFBCB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06be803a1e54d1587b4204c9e54a839b1fc7ace6","datavalue":{"value":"sum choice number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2032707$1D5DA2A4-445C-48B7-9DE3-E9E289B02EF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3a07a31336038c44367df14284b7d59ab6b018d","datavalue":{"value":"list assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q2032707$F6E12CF7-2DE8-40F5-94D0-49435F4703B9","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":"Q2032707$A63AD7A3-62E0-4033-9D34-BF2F7C335240","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"10793b9bff78eb3d77de59fbc63cf45f188e5e79","datavalue":{"value":"https://doi.org/10.1016/j.disc.2021.112391","type":"string"},"datatype":"url"},"type":"statement","id":"Q2032707$827EFE85-B233-40BD-A0E5-2AA24A1C518E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c5b349011a93f45ec05dc10f2f91d5d927a106fd","datavalue":{"value":"W3154464501","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2032707$5FF2A4BB-049A-43FC-90FB-A2AFC134E1BF","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":"Q2032707$BB87101F-C5D6-4292-978D-A0186A8E2AA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32e8bb6275bebd791db384930cc03277f6f5fe56","datavalue":{"value":{"entity-type":"item","numeric-id":2502028,"id":"Q2502028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$071E4B2C-4E8E-4192-86C6-BC213EF59EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9753601b702a61cef4086060aa216f8e2ff001ee","datavalue":{"value":{"entity-type":"item","numeric-id":3483299,"id":"Q3483299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$614BD05E-56D5-4F09-8AE1-12C3E68F557C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a606677a5d9fd709657cb45de9a96d18472c5e8a","datavalue":{"value":{"entity-type":"item","numeric-id":4411283,"id":"Q4411283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$D3BD8A76-3063-4FA8-90BC-6F78A44061F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a7d99f96f6fddec07c4695f2293474ef42a0c3e","datavalue":{"value":{"entity-type":"item","numeric-id":327690,"id":"Q327690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$A530CEA9-66D8-4AF9-9F81-79C6B620692C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cdcdd47e873c28252fc9c2c2fa401a95be81d67","datavalue":{"value":{"entity-type":"item","numeric-id":698613,"id":"Q698613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$625CDAB6-115F-4DE4-A2F0-F8426F3F02D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2e5a30974a1bd533d6cbdfea598b8502f79944","datavalue":{"value":{"entity-type":"item","numeric-id":704844,"id":"Q704844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$2E8557F8-59C7-43C7-89C6-3DD37EF64A38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7ff17aa009ed78c3a408dcdddee5ac9204c1bd9","datavalue":{"value":{"entity-type":"item","numeric-id":897250,"id":"Q897250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$5A061034-D26E-45F3-BD76-0559483AF7F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bcab9b2bfec598a791956f52d4bb8d49e3facf0","datavalue":{"value":{"entity-type":"item","numeric-id":2971199,"id":"Q2971199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$C04C034F-2508-47D9-B752-74545CB026B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c712980f9cc3ec3bab1bf01ea505a494c8c20b01","datavalue":{"value":{"entity-type":"item","numeric-id":2413335,"id":"Q2413335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$778CC035-503D-493C-B990-27E9BD37411A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ceab15bc19c6dcdb78c6c2bddfd703c741b19ad3","datavalue":{"value":{"entity-type":"item","numeric-id":916670,"id":"Q916670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2032707$759C8F8B-51D2-45DF-A153-4A174BCF6D1C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9f9428a9628106cd7ba0540caa645fe696e8c101","datavalue":{"value":"10.1016/J.DISC.2021.112391","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2032707$5353AD52-F704-4E23-B0CB-04F4E85FCCA6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50a28432604842ea24e4cbdcee4b398353437304","datavalue":{"value":{"entity-type":"item","numeric-id":2413335,"id":"Q2413335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abfa36d39a9c343012f513ad8739f2dbea8bef55","datavalue":{"value":{"amount":"+0.8874790668487549","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":"Q2032707$869D98E5-1A9E-4876-826F-5DC0B807C9D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19685a8d032411cd8cf794e2eec05eac48f18456","datavalue":{"value":{"entity-type":"item","numeric-id":327690,"id":"Q327690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50fe7c1c37535ddabaabf00690bf6bbcb6443b77","datavalue":{"value":{"amount":"+0.880338191986084","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":"Q2032707$699C5621-2B04-44FB-97AC-E99DCF9D5684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc97bfe0fb10abdb5e46e243cac758c1e75bd370","datavalue":{"value":{"entity-type":"item","numeric-id":2502028,"id":"Q2502028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65d46938fbd16a78166f1ebd458e520b370b1172","datavalue":{"value":{"amount":"+0.8479013442993164","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":"Q2032707$63A8B935-E3A9-44CC-9BBB-EA8BFDFBC1F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b4854c52b83cc32366dd0ed72de8733bca88446","datavalue":{"value":{"entity-type":"item","numeric-id":1025471,"id":"Q1025471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3919ea4ea8ae482d928fce4d77c3f9472eda76dc","datavalue":{"value":{"amount":"+0.840669572353363","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":"Q2032707$2CDCF4EA-0076-4334-A86E-5EE7FF754402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a80db87de5ca67d80d9cbe3c7a3c2015f57e573","datavalue":{"value":{"entity-type":"item","numeric-id":2799796,"id":"Q2799796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97082985e06dd7fbdc779dd5bcd8b7c5b042bc1d","datavalue":{"value":{"amount":"+0.8355717658996582","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":"Q2032707$259C4B32-71CA-4661-B9B9-FB3694565219","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2032707","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2032707"}}}}}