{"entities":{"Q2472782":{"pageid":2483525,"ns":120,"title":"Item:Q2472782","lastrevid":74183826,"modified":"2026-04-14T18:50:25Z","type":"item","id":"Q2472782","labels":{"en":{"language":"en","value":"Entropy and a certain cost-minimal coloring of graph vertices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5240245"}},"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":"Q2472782$BA9D8CA7-32E0-48EB-B26E-A5CE68FCA9D8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ab00eb59a0ad2df3b02f78477d78e1c4a9b7f96b","datavalue":{"value":{"text":"Entropy and a certain cost-minimal coloring of graph vertices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2472782$D90123EC-D8EF-46E3-A8ED-25C12A5CEE88","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"21ef6b227402a36c60c9b30647ffdb46906e482e","datavalue":{"value":"1190.90254","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2472782$D603AE14-49CC-45BA-9864-A09362733737","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aec7eb769ee0188e0b7ff5ec043ede47c484d930","datavalue":{"value":{"entity-type":"item","numeric-id":953886,"id":"Q953886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2472782$820B4404-AC66-40A0-B941-484A69103DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ed4359e771a9e93e2ac8c81fcc7069aa2f5e04e2","datavalue":{"value":{"entity-type":"item","numeric-id":2472781,"id":"Q2472781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2472782$AE80D51D-77B8-454E-8E63-90E1BF2C3F5E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"60e92c9f06012150d8158f8bfafc8319965c5fdc","datavalue":{"value":{"entity-type":"item","numeric-id":176247,"id":"Q176247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2472782$7CC4F45C-C146-400C-9916-8976660C0F8A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f94f0be27258bda14ae2c330969e222eb23a8c5e","datavalue":{"value":{"time":"+2008-02-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2472782$E5DFA0A4-5BDC-4152-9F5D-C688C9D91B54","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"90ed6f8037fc8f8e842ba5b82d53cfe607a1b1df","datavalue":{"value":"Let \\(G\\) be a graph with \\(n\\) vertices and \\(m\\) edges and let \\(c:V(G)\\to\\{1,2,\\dots,n\\}\\) be a vertex coloring. We first view \\(i\\) as the cost associated with color \\(i\\) and consider the minimum total cost \\(t(G)= \\min_c \\sum_{x\\in V(G)}c(x)\\). An inequality relation between \\(t(G)\\) and the minimum entropy \\(H(G)\\) of the color distribution induced by any coloring is obtained as \\((n/2^{H(\\overline{G})}+ 1)/2\\leq t(G)/n\\). (\\(\\overline{G}\\) is the complement of \\(G\\).) Using \\(g(G)/n\\leq m/n+1\\), we have \\(\\log(n^2/(n^2-2m))\\leq H(G)\\), and the standard argument of entropy maximization leads to a lower bound on \\(t(G)/n\\) in terms of \\(n,m\\) only. Finally, it is remarked that the results can be extended to a case of more general costs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2472782$DFDFA54C-1D96-4B50-B051-50CEECBC53D4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2472782$BA33960C-F6C5-4E38-A7E0-3C970E1379E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2472782$7D402D5D-9C45-4433-93DA-ABF4CF264C4E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eaf304be314df0fe6a34cc05673e34e8d7cf1c91","datavalue":{"value":"5240245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2472782$14016963-E1CE-4BBC-8098-0CA785B0AE2E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2472782$4680270B-0953-448F-9FD0-F0C234156D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69ff8eb4fe26637b6f80a3f7d14893a357844f18","datavalue":{"value":"cost-minimal coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2472782$5AEA46AD-E928-49B1-8E25-813ABA4FE216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb7bb40085348a7d1370b65d5af0e44f4b8311de","datavalue":{"value":"entropy bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2472782$046D2E5B-0AA2-4E09-8120-5C67AAB7AD4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e4c3963965f4d7f1eff1026582690dcd734e5c4","datavalue":{"value":"maximum entropy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2472782$FDF8CDDA-48DE-472F-9D4D-F1275DC6A487","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":"Q2472782$4653DDF8-A012-4F52-9D49-7D5677C2EBE6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c4b9af697618f1576153d46777145e39da53541c","datavalue":{"value":"https://doi.org/10.1016/j.aml.2007.01.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q2472782$31D5A0F7-8B33-4DD9-9CAC-4770EE960EA5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6ada330769de9903c5a29c719972c7370744b11b","datavalue":{"value":"W2063961221","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2472782$46B0A7DA-6649-4145-A989-4A9DEDC2F087","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1bf436c0a991acf263aff0bc0b9b9746454f4a2","datavalue":{"value":{"entity-type":"item","numeric-id":4896812,"id":"Q4896812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2472782$83791810-D505-4BB5-B9E9-85141718C769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52aff9c5eb3c4c80d652d6459a06ff8ec62dd595","datavalue":{"value":{"entity-type":"item","numeric-id":4023085,"id":"Q4023085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2472782$7E38E668-974B-4921-9055-11E2898E15FF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e5426503f9857c20e8a585e21b2d33349e07d1b7","datavalue":{"value":"10.1016/J.AML.2007.01.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2472782$4A9328C4-38EF-4070-B323-885E1B827184","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b9ac2452c4c5c86dbed6694fd5a2cadb2baeabe","datavalue":{"value":{"entity-type":"item","numeric-id":1016051,"id":"Q1016051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7c61d802f93ac080a66c067b415c45a7c9e0594","datavalue":{"value":{"amount":"+0.8314566016197205","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":"Q2472782$C6D8257B-8390-4D41-B116-51B025590A46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fa3ec336b1dbd86e6e542257458e96e90a3d3c6","datavalue":{"value":{"entity-type":"item","numeric-id":5897914,"id":"Q5897914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ddb1dd8820e2e0741a0b939bde6fbb4102cb2a1","datavalue":{"value":{"amount":"+0.8277944922447205","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":"Q2472782$FFBACFDC-E72A-450C-8D8E-B5C64A2539C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"058d27f9a2e3b795c87c3332930237c58f526278","datavalue":{"value":{"entity-type":"item","numeric-id":4522874,"id":"Q4522874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f46e3a14ef48f0534d0f32a7838aed019f6f211f","datavalue":{"value":{"amount":"+0.7508317828178406","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":"Q2472782$5C05E0E6-77D1-435E-9B74-26619548C00E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b2720821aec87e631329623d18b39ae5cb09da0","datavalue":{"value":{"entity-type":"item","numeric-id":3115192,"id":"Q3115192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d7e35bda303ac125e17ba4799130087e059eea2","datavalue":{"value":{"amount":"+0.7505931258201599","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":"Q2472782$9038C35A-B60C-4A04-8593-FCBCE65B882E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93637e50df4667c76d6399b4e72bb51a317d3f68","datavalue":{"value":{"entity-type":"item","numeric-id":960968,"id":"Q960968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5317ce76af9ca684029c4672e439726c1c001b83","datavalue":{"value":{"amount":"+0.7485805749893188","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":"Q2472782$39A44729-4CEC-46B9-9FD4-A55B61D5AA2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Entropy and a certain cost-minimal coloring of graph vertices","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Entropy_and_a_certain_cost-minimal_coloring_of_graph_vertices"}}}}}