{"entities":{"Q1759814":{"pageid":1770556,"ns":120,"title":"Item:Q1759814","lastrevid":70841106,"modified":"2026-04-13T17:37:23Z","type":"item","id":"Q1759814","labels":{"en":{"language":"en","value":"Group colorability of multigraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6109894"}},"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":"Q1759814$54F43FA5-EBFC-46C8-9814-26C9FE6AD42B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"39198dae6060cb92315bddca08f21768ed0209f6","datavalue":{"value":{"text":"Group colorability of multigraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1759814$9BF812BF-947C-421C-81A7-7AF38F875069","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aed2e128325acb625e967cab1c0d9c6fd3a0926c","datavalue":{"value":"1262.05057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759814$BAA7BDE9-AAB3-40AA-A4D3-BB4713CAAD17","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"84dbbd96058bd9a7accca3e624f3150ac3057b92","datavalue":{"value":{"entity-type":"item","numeric-id":186102,"id":"Q186102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759814$0F8BB01A-7195-4D80-A3F0-A7248924386D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e78bbd85dd0a4dfb88ff8f1784c035c3837da89e","datavalue":{"value":{"entity-type":"item","numeric-id":175486,"id":"Q175486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759814$096D36AA-B934-4B01-9DA1-AD85388B51CA","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":"Q1759814$67D24335-FA44-44AD-8CC8-5FF6860912C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2f3aa46d2f66375aad8f9f235cf6aa2da570e73e","datavalue":{"value":{"time":"+2012-11-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1759814$300E2D2D-93E0-45A8-9824-F9A2868EEE63","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4d7d2e2ecff8a6eda4729c60a328c52551c060bf","datavalue":{"value":"\\textit{R. L. Brooks'} Theorem [Proc. Camb. Philos. Soc. 37, 194--197 (1941; Zbl 0027.26403)] states that for any connected undirected graph \\(G\\) with maximum degree \\(\\Delta\\), the chromatic number of \\(G\\) is at most \\(\\Delta\\) unless \\(G\\) is a clique or an odd cycle, in which case the chromatic number is \\(\\Delta+1\\). The article under review studies group coloring as defined in the abstract.   ``Let \\(G\\) be a multigraph with a fixed orientation \\(D\\) and let \\(\\Gamma\\) be a group. Let \\(F(G,\\Gamma )\\) denote the set of all functions \\(f: E(G)\\to \\Gamma\\). A multigraph \\(G\\) is \\(\\Gamma\\)-colorable if and only if for every \\(f\\in F(G,\\Gamma)\\), there exists a \\(\\Gamma\\)-coloring \\(c:V(G)\\to \\Gamma\\) such that for every \\(e=uv\\in E(G)\\) (assumed to be directed from \\(u\\) to \\(v\\)), \\(c(u)c(v)^{-1}\\neq f(e)\\). We define the group chromatic number \\(\\chi _g(G)\\) to be the minimum integer \\(m\\) such that \\(G\\) is \\(\\Gamma\\)-colorable for any group \\(\\Gamma\\) of order \\(\\geq m\\) under the orientation \\(D\\). In this paper, we investigate the properties of \\(\\chi_g\\) for multigraphs and prove an analogue to Brooks' Theorem.''   The main theorem in this article states: ``For any connected multigraph \\(G\\), \\(\\chi_g(G)\\leq \\Delta(G)+ 1\\), where equality holds if and only if \\(G\\) is a cycle or a complete graph on \\(n\\) vertices in which each edge is replaced by \\(k\\) parallel edges, for some positive integers \\(k\\) and \\(n\\).''    Reviewer's remark: In quoting Brooks' theorem the authors omit the condition that the cycle be of odd length. This reviewer wonders whether this condition should also apply to the theorem of the article under review.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759814$0449EE54-5136-4F9F-9B21-03ADD7BF6C99","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759814$7D3C6682-895D-4EE4-97BD-C5E925BAE0FE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f03133c30e1ba5fc2c91c1ea3f5efefbd15fa191","datavalue":{"value":"6109894","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759814$963E5385-3DDF-4D0A-905C-5141EB216ED3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac2818cf7789e4bcdf8daca7a978e32e9b68ea5f","datavalue":{"value":"group coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759814$EF3ADF7A-5A47-4918-9FC4-69174D2B2FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b3544dded8c1e7ae8f05a841600daa81bbb4ce2","datavalue":{"value":"multigraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759814$DD69CF62-DE41-4923-8CF0-7ABCCE8EEE7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759814$81A87FC3-094D-4C02-B881-59C3AD2D160A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9566528450e4f92897b11bfd137e744e3ec8de58","datavalue":{"value":"Brook's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759814$114D566F-E64A-4412-B6C3-2070A553E78F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759814$CA1FDD65-0407-4E13-A40E-DCA1BBF5BAF1","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":"Q1759814$C785CE80-F600-456C-93F9-FB96DAF08F04","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"66cbb1656f36445fccd3a43b2b03cdcbb6799f9c","datavalue":{"value":"https://doi.org/10.1016/j.disc.2012.09.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q1759814$FE11D21E-7534-447D-B78C-7FF30AC0EEAF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a9efda858d63519bb811172e15928178693a1271","datavalue":{"value":"W2093572455","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759814$D633B3AA-5295-4B4C-972D-E6611CC094F0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7c1cd0973bb5b51e7d304b148550285c4399ad3d","datavalue":{"value":"10.1016/J.DISC.2012.09.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759814$3E712B46-4917-4569-A5D2-B3F8621E3D9F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a88c461e0dcbf7db9397b65aa96bf8e5cf5355b","datavalue":{"value":{"entity-type":"item","numeric-id":5461502,"id":"Q5461502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ac950589df6d8c2f4831769b05ef3883581bbd0","datavalue":{"value":{"amount":"+0.8107531666755676","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":"Q1759814$42148E84-D379-441F-88F6-45954253CD4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1502cd6863ac8ac1e5c715db7af85ed6badf4270","datavalue":{"value":{"entity-type":"item","numeric-id":5706477,"id":"Q5706477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f462bca44948022d360ed39172242217176aca13","datavalue":{"value":{"amount":"+0.7995938062667847","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":"Q1759814$044E6AA4-E997-46F3-96B2-33D8F736AFF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4eb72a166bdf1e2f5daa1af37db8a5926366840e","datavalue":{"value":{"entity-type":"item","numeric-id":2462377,"id":"Q2462377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"287152eb3aace1afaa45cf0e50d979ab34bb73dd","datavalue":{"value":{"amount":"+0.7622328996658325","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":"Q1759814$D876FEA9-7B73-4AD1-B929-2FCF6DE41FD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bcbac6987ddb82736f502a05f900b70590a8a4a","datavalue":{"value":{"entity-type":"item","numeric-id":5379843,"id":"Q5379843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa1fb6920a9ab9b9c8ca8b45789961124e60d455","datavalue":{"value":{"amount":"+0.7558870315551758","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":"Q1759814$642953EF-736B-499F-8FC1-1E396F4B2A6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4830f11ef2902874784b7c96431d408f324f4776","datavalue":{"value":{"entity-type":"item","numeric-id":2494108,"id":"Q2494108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02e852c03fad8b6f9f314653dfeffc66b8704ecc","datavalue":{"value":{"amount":"+0.7548983097076416","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":"Q1759814$A17A3EEF-98AA-46CB-94EC-C155D9F0B076","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Group colorability of multigraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Group_colorability_of_multigraphs"}}}}}