{"entities":{"Q2380243":{"pageid":2390986,"ns":120,"title":"Item:Q2380243","lastrevid":72652425,"modified":"2026-04-14T06:19:02Z","type":"item","id":"Q2380243","labels":{"en":{"language":"en","value":"Bounds on the distinguishing chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5686791"}},"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":"Q2380243$F5D20CD1-9FAE-4AF8-AC8A-1B76DB56140B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8415df4a04fd368394a0f283ef29ed01e117c837","datavalue":{"value":{"text":"Bounds on the distinguishing chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2380243$0A033D8B-628B-40EB-BB78-BC634F350BA3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9211e58d6d0548fed9e347c874e881b6eac81259","datavalue":{"value":"1186.05051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380243$00DDBEB7-844F-40F7-B36C-684280CCF473","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a80f0a30c34568b1594b2aaace08fe6b51a1e6b","datavalue":{"value":{"entity-type":"item","numeric-id":234314,"id":"Q234314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380243$DB1BEAED-D8AF-4FFE-825D-2A7F7331E15C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d32bdb43352779c472e08e65787c883d867f4a6","datavalue":{"value":{"entity-type":"item","numeric-id":251908,"id":"Q251908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380243$685DFEE1-8030-4AC6-8C1C-58D038F821CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"999d73895bab7bd80bfc2ada78ef4ecc1c4775b6","datavalue":{"value":{"entity-type":"item","numeric-id":1362081,"id":"Q1362081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380243$8D995E88-C59E-4A0C-8B87-B10ABA4D6F4E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380243$22BF5D8F-2B62-4C58-A1D5-9CEBC5B9D006","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"143e8774a45e663375c24b3b343519cf2933b18c","datavalue":{"value":{"time":"+2010-03-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":"Q2380243$F909A9CD-D58B-413B-A67B-4DB18A362201","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e5387c8541c786e9c8ab78a88ae377da4927cf2c","datavalue":{"value":"https://eudml.org/doc/224898","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380243$0AF99118-4FA2-4A05-8CC1-BEDAAB6624E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"e7a79a40e3747f5b411b1540add947101d0e4423","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r88.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380243$9A2C97A8-F6D7-40E0-B7DF-9131E887276B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c27a3c113ec8dba55bd55fe9274a9dc8ad74b6fc","datavalue":{"value":"Summary: Collins and Trenk [\\textit{K.L. Collins} and \\textit{A.N. Trenk}, ``The distinguishing chromatic number'', Electron. J. Comb. 13, No. 1, Res. paper R16 (2006; Zbl 1081.05033)] define the distinguishing chromatic number \\(\\chi_D(G)\\) of a graph \\(G\\) to be the minimum number of colors needed to properly color the vertices of \\(G\\) so that the only automorphism of \\(G\\) that preserves colors is the identity. They prove results about \\(\\chi_D(G)\\) based on the underlying graph \\(G\\). In this paper we prove results that relate \\(\\chi_D(G)\\) to the automorphism group of \\(G\\). We prove two upper bounds for \\(\\chi_D(G)\\) in terms of the chromatic number \\(\\chi(G)\\) and show that each result is tight: (1) if \\(\\Aut(G)\\) is any finite group of order \\(p_1^{i_1}p_2^{i_2}\\cdots p_k^{i_k}\\) then \\(\\chi_D(G)\\leq \\chi(G)+ i_1+i_2+\\cdots+ i_k\\), and (2) if \\(\\Aut(G)\\) is a finite and abelian group written \\(\\Aut(G)= \\mathbb Z_{p_1^{i_1}}\\times\\cdots\\times \\mathbb Z_{p_k^{i_k}}\\) then we get the improved bound \\(\\chi_D(G)\\leq \\chi(G)+k\\). In addition, we characterize automorphism groups of graphs with \\(\\chi_D(G)=2\\) and discuss similar results for graphs with \\(\\chi_D(G)=3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380243$4DBB52BD-A91C-4F0A-A2EE-5A8EA9ADED3A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380243$179F1F55-4F28-4260-A8A8-49198A6E38D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380243$D0AA0DE4-64D1-43C9-80FA-ACE90F2053FD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3b942deeb9ff2c2a49ed8ba8c303f624a85379c9","datavalue":{"value":"5686791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380243$347B6656-9A78-4BA8-A31B-63877494E374","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c0140de3f08eb78ec7999a29727e9d8a4f3a187","datavalue":{"value":"distinguishing chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380243$C12D293D-DA3E-440E-90B6-07FE08C233D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7004ea3c45e788d894ca43ad9fb77d664ad32ef0","datavalue":{"value":"automorphism group","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380243$DE604222-4047-40B7-8AEC-40F67D09746C","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":"Q2380243$AAF7D332-FC22-43B4-904A-73BAA8831785","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"a0e4a3caf6910be30050129a7e5e11b7828a47a0","datavalue":{"value":"bafkreigccclmkfcriwrpnxgdsqznv4ktdeauiln45j53avgtn2mkr7uif4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380243$0B42CDFC-705F-425B-A3CF-76AE7C55AE62","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49e6da968a224e6bd795795dbca9bf667356fba8","datavalue":{"value":{"entity-type":"item","numeric-id":1953399,"id":"Q1953399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"764d44a7f38da0de86fa5a2004813a21ca678a5d","datavalue":{"value":{"amount":"+0.8613840937614441","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":"Q2380243$FA5F51F1-81A8-4B43-9CAD-B819D97A674A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb2e86756ed25bb60f59485f690b16d524f7676b","datavalue":{"value":{"entity-type":"item","numeric-id":5357291,"id":"Q5357291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6b6dd13eb2e2376ff037e0ec18d2f4c49e092ef","datavalue":{"value":{"amount":"+0.8502411842346191","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":"Q2380243$243E05A6-AC70-442A-96E3-37A68A2B6BBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f0145626f768df0d464b2e04a8d8bcfb324366c","datavalue":{"value":{"entity-type":"item","numeric-id":815210,"id":"Q815210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"866cfa9c08278381ea522fdcd8a66304e3517d7b","datavalue":{"value":{"amount":"+0.8483266830444336","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":"Q2380243$D8DC43DF-E2A0-4D85-8B74-CB47B767B838","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f2e0936dd683d70da97e6d1b3e9b73c9085f139","datavalue":{"value":{"entity-type":"item","numeric-id":5217075,"id":"Q5217075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69056853f7f5205a2757e5c507abd73cc81be4b7","datavalue":{"value":{"amount":"+0.8409573435783386","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":"Q2380243$DF8A781E-2443-4CDB-94BC-C32912271CB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"995ab5d625565e71a9169edb91da924ff93310e4","datavalue":{"value":{"entity-type":"item","numeric-id":1953404,"id":"Q1953404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"740c466478f51b65166323d47a46c97b8b77fe77","datavalue":{"value":{"amount":"+0.8234657645225525","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":"Q2380243$1281F37D-96BB-4D94-9A61-4A03B96F141F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounds on the distinguishing chromatic number","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounds_on_the_distinguishing_chromatic_number"}}}}}