{"entities":{"Q5964985":{"pageid":8141787,"ns":120,"title":"Item:Q5964985","lastrevid":52468865,"modified":"2026-01-22T17:46:02Z","type":"item","id":"Q5964985","labels":{"en":{"language":"en","value":"Max-coloring of vertex-weighted graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6548083"}},"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":"Q5964985$B7298655-D7A2-40E4-9B9F-4272109B80E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1d94bcec02c74768fb9613aaa1ac6eea0bdf0a4b","datavalue":{"value":{"text":"Max-coloring of vertex-weighted graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5964985$DD9FF549-5E15-4CB4-AC62-C9415DFB8554","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a5adc96c5faabc1e50eb39dced3ff6e0da4bbab4","datavalue":{"value":"1341.05075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5964985$A6309168-9A30-4ED9-AA71-26541EFD203F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"899ee08cfa5a78ecc957d1e62cb5bbc4f196ef83","datavalue":{"value":{"entity-type":"item","numeric-id":251522,"id":"Q251522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$58EA23BA-9881-4310-B4E8-F6686BD850ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b01296838df87730769f910acaeeb4756766580","datavalue":{"value":{"entity-type":"item","numeric-id":400523,"id":"Q400523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$BA3331BC-3E7F-4F33-9B14-4A06661DCAD0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$F621D6C6-54D6-4D74-921D-4B3522CCE3BD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2cbcbddb948a4fe301f67374c57ebdb5a8dfc5b4","datavalue":{"value":{"time":"+2016-03-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5964985$25C36239-9C40-4E19-8247-CD9A4B743AF4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b4aebdb91148921a63357e178ee2f7bdec6515fc","datavalue":{"value":"A proper vertex coloring of a graph \\(G\\) is a partition \\(\\{A_1, \\dots, A_k\\}\\) of the vertex set \\(V(G)\\) into stable sets. For a graph \\(G\\) with a positive vertex weight \\(c: V(G) \\to (0, \\infty)\\), denoted by \\((G, c)\\), let \\(\\chi (G, c)\\) be the minimum value of \\(\\sum_{i = 1}^k \\max_{v \\in A_i}c(v)\\) over all proper vertex colorings \\(\\{A_1, \\dots, A_k\\}\\) of \\(G\\) and \\(\\natural\\chi(G, c)\\) the minimum value of \\(k\\) for a proper vertex coloring \\(\\{A_1, \\dots, A_k\\}\\) of \\(G\\) such that \\(\\sum_{i = 1}^k \\max_{v \\in A_i}c(v) = \\chi(G, c)\\). In this paper, the author establishes an upper bound on \\(\\natural\\chi(G, c)\\) for a weighted \\(r\\)-colorable graph \\((G, c)\\). A Nordhaus-Gaddum type inequality for \\(\\chi(G, c)\\) is also proved. The following results are proved in the context of perfect graphs.   Theorem. A graph \\(G\\) is \\(c\\)-perfect for all vertex weights \\(c\\) if and only if it is a complete \\(r\\)-partite graph for some \\(r\\).   Theorem. If \\(G\\) is \\(P_4\\)-free (or equivalently a cograph), then \\(G\\) is \\(c\\)-perfect for any vertex-weight \\(c\\) satisfying \\((C1)\\) for any three vertices \\(x, y, z\\) among which there is exactly one edge \\(yz\\), we have \\(c(x) \\leq \\max\\{c(y), c(z)\\}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5964985$90EF9DCF-83E2-4601-BFA5-B5B6230A06F7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"34ca366c7bb277434f612f766d36fa16b74d5cf2","datavalue":{"value":{"entity-type":"item","numeric-id":657386,"id":"Q657386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$DF4F8506-5E47-47C6-B6CB-B201E9AE2F5E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5964985$73C968F1-A8B2-4790-8170-830F21155D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b2773d305bb22ed635d748bc939993c6750608ab","datavalue":{"value":"05C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5964985$E86E6A30-59B8-4D3B-A185-4D0978614B3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5964985$530D415A-F66C-49C6-9FDE-AF9517FAD7D8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"451841030272877a61828d4a50634880ae3c6142","datavalue":{"value":"6548083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5964985$2B54FA38-CE87-45CB-8009-60A9A442F46D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5964985$CC3FEA3E-0E61-46C7-B731-585108BA8B9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b760e16052dafa055937db475a4d93deb5356285","datavalue":{"value":"weighted graph, perfection","type":"string"},"datatype":"string"},"type":"statement","id":"Q5964985$1B478740-4E6F-4DE9-8557-E8DA433D56AC","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":"Q5964985$79F7AF3D-C39D-40A3-8681-81575F2C4BA1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f96b079ef122aacc92768c03b5e2f1e920ed0c39","datavalue":{"value":"https://doi.org/10.1007/s00373-015-1562-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q5964985$7A86AAFC-E5B6-4269-915A-274786E77F99","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d436c73214c397479fb06c3536c1319009dce9f0","datavalue":{"value":"W2108741137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5964985$4B4B6092-838D-4763-81B4-00F3335DCECD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"55b9ff904e1c98a6431855b40a7e673c55670f79","datavalue":{"value":{"entity-type":"item","numeric-id":4097267,"id":"Q4097267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$95F7C75D-A4F4-4FA2-A93D-7805BE1C9E97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dee784204011c46a17824e3437394bed4cc16f1b","datavalue":{"value":{"entity-type":"item","numeric-id":4414490,"id":"Q4414490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$EB69F993-EF0B-46DD-92CF-97C78793BB6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8f287f63663cad2fcbd52a1da7341f5bfa9b0c5","datavalue":{"value":{"entity-type":"item","numeric-id":1045908,"id":"Q1045908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$4FC06CD2-1723-4058-8638-9CB30A0D149E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"904fbef47fb47aeed5d61932cfa523281bd82c37","datavalue":{"value":{"entity-type":"item","numeric-id":286971,"id":"Q286971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$DA2F612D-7778-41FC-AEA6-51F71B37DFFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23d93b01e42f41117fe74307a56352640b573a64","datavalue":{"value":{"entity-type":"item","numeric-id":925259,"id":"Q925259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$F97977AB-B634-404F-8BA2-D98F6185C43A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"670b078818e8e26dc47a5865d6ba1d0b10debbce","datavalue":{"value":{"entity-type":"item","numeric-id":5716853,"id":"Q5716853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$EEB33E8D-4C0A-4AE5-AE66-259211DA7788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d369953ffba2e103be1dac992d6e69629fd65376","datavalue":{"value":{"entity-type":"item","numeric-id":5501309,"id":"Q5501309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$AE58F2A1-015F-4A7C-8951-A01576957244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fee00e8b348bfcf4c4329d09406bc31ade693322","datavalue":{"value":{"entity-type":"item","numeric-id":1028481,"id":"Q1028481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5964985$0B5C1424-FBF1-4A78-8D89-7B93BCA422A5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ad3220f9a19defeac543ae5da1819a59b77736a1","datavalue":{"value":"10.1007/S00373-015-1562-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5964985$27BA4EF7-04E0-4970-B612-43D36D68D045","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dda63c6006414ec732071b10595ffee8a69d2b9","datavalue":{"value":{"entity-type":"item","numeric-id":1045908,"id":"Q1045908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97da3588378d6936f2b05e495d8fe6c06b7f21d5","datavalue":{"value":{"amount":"+0.806106686592102","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":"Q5964985$9457048F-8F45-4EB4-9B69-0040C685B585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eedd9c09dbf5062b93f065d5acb223c87ab9f8eb","datavalue":{"value":{"entity-type":"item","numeric-id":5395073,"id":"Q5395073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bcb68cf57c607f88b0e238890ec7de8c0746d2f","datavalue":{"value":{"amount":"+0.8045486211776733","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":"Q5964985$8894BA71-58C9-4DFF-B6ED-3BC219B3C615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4469d27cb4485c3f620c863b1054057d992a36eb","datavalue":{"value":{"entity-type":"item","numeric-id":286971,"id":"Q286971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27e5416eca809ba568647fa10667531414353273","datavalue":{"value":{"amount":"+0.7788269519805908","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":"Q5964985$7CEE33E4-52A0-4708-9BC2-1BC0FB576915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f0ec6459519f299a56dc8397e357042775cf477","datavalue":{"value":{"entity-type":"item","numeric-id":3115650,"id":"Q3115650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"627fdf8d2463aa3ba2fc1e2aba7abb5c1caa61f0","datavalue":{"value":{"amount":"+0.7768643498420715","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":"Q5964985$C926AFD3-FECD-40D5-9C91-AAC297641633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b203913ffcc14ebce21e18b88c2bde0f14e9de3","datavalue":{"value":{"entity-type":"item","numeric-id":5284584,"id":"Q5284584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c88a44649dfa68be9782dee900548f8ef1103fb","datavalue":{"value":{"amount":"+0.7687744498252869","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":"Q5964985$7F9DC978-58A3-46E6-A2A7-671101CD3568","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5964985","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5964985"}}}}}