{"entities":{"Q6045131":{"pageid":13179287,"ns":120,"title":"Item:Q6045131","lastrevid":93756434,"modified":"2026-06-05T05:03:12Z","type":"item","id":"Q6045131","labels":{"en":{"language":"en","value":"Upper bounds on the average number of colors in the non-equivalent colorings of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7689548"}},"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":"Q6045131$68874A8D-7450-49EC-9D8E-99971DFC86A1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ca615c65e3f232a1509350797163b3bafff7236","datavalue":{"value":{"text":"Upper bounds on the average number of colors in the non-equivalent colorings of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6045131$0C68F41E-C529-4023-B565-D9F52A9A9248","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b7403298c987c275d43ddab879b5b8909c40b53c","datavalue":{"value":"1518.05064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6045131$4D72E768-73EC-4D77-984B-DEAF7DD57EB6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4249c9a7a0b14df0599e70315ca2a040457d857c","datavalue":{"value":{"entity-type":"item","numeric-id":260023,"id":"Q260023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$C616EEA9-7162-4561-855B-2F98D6AD0590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"28e4938eeb5403fc95a8bf709a2057d46b7b0e38","datavalue":{"value":{"entity-type":"item","numeric-id":260024,"id":"Q260024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$CD4922D0-1075-4B6F-8852-F4313ABEF340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"306a12ed49e148ad3032b79058b6371c3560e501","datavalue":{"value":{"entity-type":"item","numeric-id":6045130,"id":"Q6045130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$9C2A8600-5822-4FB3-9A6D-EAE9EAFD4114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"77585105a2aa80f7b79c86ebce2a582145bf9d49","datavalue":{"value":{"entity-type":"item","numeric-id":2274081,"id":"Q2274081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$D3E5A766-9B96-49B6-8A85-DA6CAC841EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0e7ff0ef7beddf35335a6b15de45b4bb6411a85d","datavalue":{"value":{"entity-type":"item","numeric-id":2274080,"id":"Q2274080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$6993082F-3C21-4DDA-AB7A-AF32F4BFD146","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":"Q6045131$7F892D5F-FBF1-4FB2-88D3-63446077C422","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9e202514302232ff7f5ec81097f072c587f02b43","datavalue":{"value":{"time":"+2023-05-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6045131$DC17BB18-F27A-44B8-94A1-B1BFDD4B662E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7ea3ecc994e0c0910e773860d7307af5b9025296","datavalue":{"value":"https://arxiv.org/abs/2105.01120","type":"string"},"datatype":"url"},"type":"statement","id":"Q6045131$CA370B7D-BBB1-4349-B399-EB6D216229F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"077fb0c7d3ff96a9a539d3943dc6633b00c75fbe","datavalue":{"value":"A \\(k\\)-coloring of a graph \\(G\\) is a mapping \\(c:V(G) \\to \\{1,2,\\ldots ,k\\}\\) such that \\(c(u)\\neq c(v)\\) for any pair of adjacent vertices \\(u\\) and \\(v\\). Two colorings are equivalent if they induce the same partition of \\(V(G)\\) into color classes. In the paper, the following notations are used. \\(S(G,k)\\) is the number of non-equivalent \\(k\\)-colorings of \\(G\\) and \\({\\mathcal{B}}(G)=\\sum_{k=\\chi(G)}^n S(G,n)\\) is the total number of non-equivalent colorings of \\(G\\). Moreover \\({\\mathcal{T}}(G)=\\sum_{k=\\chi(G)}^n kS(n,k)\\) is the total number of color classes in all non-equivalent colorings of \\(G\\) and \\({\\mathcal{A}}(G)=\\frac{{\\mathcal{T}}(G)}{{\\mathcal{B}}(G)}\\) is the average number of colors in the non-equivalent colorings of \\(G\\).  The authors of the paper study the upper bounds of \\({\\mathcal{A}}(G)\\) in terms of the order \\(n\\) of a graph \\(G\\). They show trivial upper bound \\({\\mathcal{A}}(G) \\leq n\\) and \\(K_n\\) is the only graph achieving the bound. For graphs with maximum degree \\(\\Delta(G) \\in \\{1,2,n-2\\}\\) better upper bounds are presented. For graphs with \\(\\Delta(G)=n-2\\) they prove that \\({\\mathcal{A}}(G) \\leq \\frac{n^2-n+1}{n}\\), where the equality holds just for a graph \\(G\\) isomorphic to \\(K_{n-1} \\cup K_1.\\) For graphs with \\(\\Delta(G) \\in \\{1,2\\}\\) they present a graph \\(H\\) of order \\(n\\) with the largest \\({\\mathcal{A}}(G)\\) between all graphs of order \\(n\\) and thus bound average number of colors in the non-equivalent colorings of arbitrary graph with given maximum degree not with the exact function of \\(n\\) but with \\({\\mathcal{A}}(H)\\). For graphs \\(G\\) with \\(\\Delta(G)=1\\) it is proved that \\({\\mathcal{A}}(G) \\leq {\\mathcal{A}}(\\lfloor \\frac{n}{2} \\rfloor K_2 \\cup (n \\bmod 2)K_1)\\) and that graphs \\(\\lfloor \\frac{n}{2} \\rfloor K_2 \\cup (n \\bmod 2)K_1\\) are the only graphs achieving this bound. Finally, for graphs \\(G\\) with \\(\\Delta(G)=2\\), the authors prove the average number of colors in non-equivalent colorings of a graph \\(G\\) of order \\(n\\) is bounded above by \\({\\mathcal{A}}(U_n)\\), where \\(n \\geq 3\\) and \\(U_n=\\frac{n-1}{3}K_3 \\cup K_1\\), if \\(n \\in \\{4,7\\}\\), else \\(U_n=\\frac{n}{3}K_3\\) if rem\\((n,3)=0\\), \\(n \\geq 3\\), else if rem\\((n,3)\\in \\{1,2\\}\\), then \\(U_n= \\frac{n-3-\\textrm{rem}(n,3)}{3}K_3 \\cup C_{3+rem(n,3)}\\). It is also proved that \\(U_n\\) is the only graph of order \\(n\\) for which the average number of colors in the non-equivalent colorings is \\({\\mathcal{A}}(U_n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6045131$32724EDD-A8D5-43D1-9290-FFD45549B8A4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"512183e69be4ab0f9c803f93e55f4d9b77753376","datavalue":{"value":{"entity-type":"item","numeric-id":504963,"id":"Q504963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$DE79FB53-ED44-497D-9473-A2F014B143A8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6045131$BC67061D-D2A0-4D84-887F-2088078A5362","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"be94ab264c61cb7ef5484182fb37af4a59f93cf9","datavalue":{"value":"7689548","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6045131$69BBF892-2617-4397-9BA7-C2609EDBA6D7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6045131$C47DDFE4-552E-4FE2-A916-1F2BBB59ABA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3f0bc98a942804b4c575f12a81186ba7db1d2fa","datavalue":{"value":"average number of colors,","type":"string"},"datatype":"string"},"type":"statement","id":"Q6045131$13DDD5DA-6DB2-41C3-A373-77834044F0E5","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":"Q6045131$898D8F48-CF56-4B02-94EE-9A338ADAEB8C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ae1f036e6b762d368f26f131ebea6e61bacdc05e","datavalue":{"value":"W3159107677","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6045131$5482C5D2-6564-4475-B93A-C7561F81707A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce1df8adce82e6e26c5e2ff39fc05eabca1f2f5a","datavalue":{"value":{"entity-type":"item","numeric-id":1686044,"id":"Q1686044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$419A34F1-259C-485E-9E47-AD6A55571863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9bd736148b99b371328462bf1d6249543dba023","datavalue":{"value":{"entity-type":"item","numeric-id":5272625,"id":"Q5272625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$3DBF3B54-1570-4680-860D-DCC034CD5C1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b24888992e3a237adbc5dc82a15c7daf18e72276","datavalue":{"value":{"entity-type":"item","numeric-id":5313291,"id":"Q5313291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$2B3B1E1E-4AA8-4267-8599-A79A1223E349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae39a79dc40ab79de2b8226426cfc6133ea265bc","datavalue":{"value":{"entity-type":"item","numeric-id":2995169,"id":"Q2995169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$D32FF347-53C1-450C-86BA-5C3992D0D8B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a24519d4921db2866d17bcfd9b9f0345e5b7096","datavalue":{"value":{"entity-type":"item","numeric-id":3550089,"id":"Q3550089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$394FFFE4-C819-49F4-9AA7-5CBDE821B1E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35d38332a0a2779f213fbaa9179203cdd9e06486","datavalue":{"value":{"entity-type":"item","numeric-id":1953467,"id":"Q1953467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$63087AC2-8710-4BCA-9A61-FB6A637C2DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39ef7be2e83d0f0bdf3ebecbb284580b670c75eb","datavalue":{"value":{"entity-type":"item","numeric-id":5026930,"id":"Q5026930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$89C12CDE-38E8-422A-9DCD-9F7DAE17B375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17bd83cfa9f5b157f0721b8efa4bf1876f26e4a1","datavalue":{"value":{"entity-type":"item","numeric-id":260025,"id":"Q260025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$C1A4D092-38D0-448F-A14F-8DF06543E243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b55fd72a18714d72b30084d51e960891c65e8ca6","datavalue":{"value":{"entity-type":"item","numeric-id":6046133,"id":"Q6046133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$DE7EA927-C145-438E-9400-BB8436DF37CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa9bb29d6031b7316c96bc6f9bfa6ef09f59b08c","datavalue":{"value":{"entity-type":"item","numeric-id":2875496,"id":"Q2875496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$B1601239-13E7-4955-B5AF-22BAF10B1659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8a3602776e3b7cb21fed9137d6c8e0878aa7cc5","datavalue":{"value":{"entity-type":"item","numeric-id":1063598,"id":"Q1063598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$BCCCAB30-7765-44B0-9D28-CD287FE2483A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbfe8b3db045c3af5bd936077fb2e74b1125b562","datavalue":{"value":{"entity-type":"item","numeric-id":4443440,"id":"Q4443440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6045131$788185B5-4440-45ED-A517-81CD8600EE90","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b47a367d6f59bbbf21e6db6c7b5f85e69c17496b","datavalue":{"value":"10.1007/S00373-023-02637-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6045131$353ED71C-D2AD-4DF9-AD97-B02705DC4FBB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2986de461ac5c00c4b6c8e24dc8fececbcf3dfb","datavalue":{"value":{"entity-type":"item","numeric-id":6046133,"id":"Q6046133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7301d8a8ec2c6a7ee03dd5c72e35c76168dbc4ae","datavalue":{"value":{"amount":"+0.889252781867981","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":"Q6045131$707DF0A5-45AE-4B0A-A1A5-3A3D09F194FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de20db7e601e008e6ea471f91f14b4a357444419","datavalue":{"value":{"entity-type":"item","numeric-id":260025,"id":"Q260025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e85da1ca51b24d5f1f035628472c58fc5f480290","datavalue":{"value":{"amount":"+0.8481305837631226","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":"Q6045131$D456B63C-5FE1-415D-8617-8722C3A840C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"071eb93bab0d8649f87097425be80c9b8ad8c2d4","datavalue":{"value":{"entity-type":"item","numeric-id":1686044,"id":"Q1686044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6c5af9d668082073e21505da53ab8e1912c0d1b","datavalue":{"value":{"amount":"+0.8336175680160522","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":"Q6045131$63CEBF0E-E9D8-4228-AA19-0777C25D3039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c978c7640e7a4153e54438fa0c17cca805161aa","datavalue":{"value":{"entity-type":"item","numeric-id":1405125,"id":"Q1405125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f425fde6172b3f085b12b9bd036613d50db37edc","datavalue":{"value":{"amount":"+0.7712042927742004","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":"Q6045131$25CAFD01-86B5-4B53-8B79-10702285161D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c9881533e8df3092c42168cf26a63f36b51fd59","datavalue":{"value":{"entity-type":"item","numeric-id":2828915,"id":"Q2828915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"228e81c024d5aae383dafb040e2760ea3007ebb4","datavalue":{"value":{"amount":"+0.768413782119751","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":"Q6045131$36F8E1DE-44B6-408A-A650-11AF9D79CDF7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Upper bounds on the average number of colors in the non-equivalent colorings of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Upper_bounds_on_the_average_number_of_colors_in_the_non-equivalent_colorings_of_a_graph"}}}}}