{"entities":{"Q1658779":{"pageid":1669520,"ns":120,"title":"Item:Q1658779","lastrevid":71779965,"modified":"2026-04-14T00:29:39Z","type":"item","id":"Q1658779","labels":{"en":{"language":"en","value":"Proper distinguishing colorings with few colors for graphs with girth at least 5"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6918062"}},"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":"Q1658779$0A1830C0-81F3-47CC-9F17-E9737CC5C666","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"39a60438a0826264ce5cdd66780126cadee03be1","datavalue":{"value":{"text":"Proper distinguishing colorings with few colors for graphs with girth at least 5","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1658779$767CF09B-27C1-4739-9812-0155FB0F7F19","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c34cc4d8b03eaa838ed8324e7d4cdd19aa97f4ab","datavalue":{"value":"1393.05109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1658779$2B3D7792-81FF-4842-A1E8-9FD4EEA3128F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae41f04ca594ca85b65fe9b038c9fd67cd961e89","datavalue":{"value":{"entity-type":"item","numeric-id":311578,"id":"Q311578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$AD1DA765-FA5D-490B-B95F-C5D66350C8B3","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":"Q1658779$1C254999-C623-445D-BC98-C175550724CA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"db9626bb787427167dc8802eb63a193ac3c35362","datavalue":{"value":{"time":"+2018-08-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1658779$7E5300A8-0F5D-45DC-858A-37081F6E11D0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"84c4ad6202a653a580f348a80b81a8d2e32d3ed1","datavalue":{"value":"https://arxiv.org/abs/1707.05439","type":"string"},"datatype":"url"},"type":"statement","id":"Q1658779$D038F688-5E83-4EED-AA94-090DC1D0214F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"7bdff4baf13a5608a3a3ef57acc4b65148ebeb32","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1658779$7744AED8-5B98-410A-BA75-3B20B9FE8124","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"43280d7f00437a0b67f49a6f8094938a7f3b9113","datavalue":{"value":"Summary: The distinguishing chromatic number, \\(\\chi_D(G)\\), of a graph \\(G\\) is the smallest number of colors in a proper coloring, \\(\\varphi\\), of \\(G\\), such that the only automorphism of \\(G\\) that preserves all colors of \\(\\varphi\\) is the identity map. \\textit{K. L. Collins} and \\textit{A. N. Trenk} [Electron. J. Comb. 13, No. 1, Research paper R16, 19 p. (2006; Zbl 1081.05033)] conjectured that if \\(G\\) is connected with girth at least 5 and \\(G\\neq C_6\\), then \\(\\chi_D(G)\\leqslant \\Delta+1\\). We prove this conjecture.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1658779$A6630BE7-77DD-4489-B977-57D7FF0C5FEC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1658779$9E84C642-A9B4-4199-B84A-148C9DDBDF47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1658779$FF0B7730-B4AF-43CB-9A86-17A3CB9F4056","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"15e0d7a1272ab50dc1151bc22764924193586c64","datavalue":{"value":"6918062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1658779$7149C0D6-FDF7-4A2B-8C19-25A4E90F0D89","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c0140de3f08eb78ec7999a29727e9d8a4f3a187","datavalue":{"value":"distinguishing chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1658779$14921A3D-A131-4A2A-A322-00F8A27F4DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce7ab89ef0afcd2141c7da8aae338608bd16ac9a","datavalue":{"value":"automorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1658779$E666E185-2A75-4C7E-ACEA-30C4CA08DB18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb3e3bb8b0c036a623403117c28f4237a7417347","datavalue":{"value":"distinguishing coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1658779$800D0BBA-0B18-4FF4-86EB-8EB58B9E6132","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5f805722941d9d651598b657c08cf8022400fa4","datavalue":{"value":"girth 5","type":"string"},"datatype":"string"},"type":"statement","id":"Q1658779$322F322E-6445-432C-AFBD-863793D74E9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834ef099fddf744c066723f952f8e825befc12c4","datavalue":{"value":"greedy coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1658779$24F4E19A-E539-483B-9BB2-D18005470C5A","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":"Q1658779$D66CDDCF-152B-41C3-9C9E-5488272D669E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f2b6d5b6b5032480f66450f129074fda80e1421","datavalue":{"value":{"entity-type":"item","numeric-id":1649920,"id":"Q1649920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$C5F38073-2A7B-49C3-BB96-09678261FF2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1c0858247d908dd5e3fd01d4d9c863c992769d5","datavalue":{"value":{"entity-type":"item","numeric-id":1953399,"id":"Q1953399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$DB2548F7-384F-4A6A-87F3-FF02BCBD0E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60b268f1864fbdc90dceea7e74710ad96ba322a9","datavalue":{"value":{"entity-type":"item","numeric-id":1044994,"id":"Q1044994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$F86AC096-5C9E-412C-BA07-77039F16FEEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af7ef0d2104c6fdf226b9a03410043120e5aa415","datavalue":{"value":{"entity-type":"item","numeric-id":3084214,"id":"Q3084214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$6BCBEEF0-72D1-4D33-8E75-C884D0211A7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e64f43320f985ffdadca489263dbf92edb05478","datavalue":{"value":{"entity-type":"item","numeric-id":2380243,"id":"Q2380243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$0FF77231-9522-4238-A336-7F38648A4AAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fad054570a463afcdd43da51b1cf712b854fcb25","datavalue":{"value":{"entity-type":"item","numeric-id":815210,"id":"Q815210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$8576BDBF-BACC-4A89-9A35-312B1F54B3F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7723020b0d451e38bb3ed6f816310659a5dc766d","datavalue":{"value":{"entity-type":"item","numeric-id":684119,"id":"Q684119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$D40F6DE3-6E99-40C7-ABC7-DFF5727B5D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c304993fcfcb4248606fa81cbf684a6f87f3730","datavalue":{"value":{"entity-type":"item","numeric-id":2380231,"id":"Q2380231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$F9FB51DE-0B20-4AFA-ADF8-28021D69D4B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"683d72f6bfe7e0ce58dce6d08905b43927e68559","datavalue":{"value":{"entity-type":"item","numeric-id":4198797,"id":"Q4198797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$781AFC88-7608-4C28-A0C9-DFCDFEEDA472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92077b84d7a6aabab7f2ca3e178b3e89c72e8c83","datavalue":{"value":{"entity-type":"item","numeric-id":2380291,"id":"Q2380291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1658779$BF60BCD0-4829-463B-BEE5-ACF4902B40EA","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"cee64f2697f2d742c69b42f148de633aa27797cd","datavalue":{"value":"bafkreigqh5qf2yplxsf2ticwi3gx6ugl2iqxtpchwehp5ehg5lwauraexq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1658779$626290C7-69B9-46B1-BB25-CA836E7052C0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8e1f751430dc6ac407c0a430fb801cb8b24653c","datavalue":{"value":{"entity-type":"item","numeric-id":5122711,"id":"Q5122711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1eb1b0b6ccdc63866879bd5b2930cae5e79d3920","datavalue":{"value":{"amount":"+0.8457350730895996","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":"Q1658779$82A2FBC3-7618-4BCC-9A1E-1ED384A0FF83","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":"945968e77aff6e3197f19ddb3561528dbe32d04e","datavalue":{"value":{"amount":"+0.8225198984146118","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":"Q1658779$1488752E-1170-4688-9717-C52B78C35AF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cafc619b7348cbd5a9c7a57bc945b94fd20a8239","datavalue":{"value":{"entity-type":"item","numeric-id":489739,"id":"Q489739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"425e31631f525dba2709440520727ca6a693637b","datavalue":{"value":{"amount":"+0.82051682472229","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":"Q1658779$853D88C2-F32E-4D8C-AC39-ADC2F5E88D41","rank":"normal"},{"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":"a3a64673eafc18bfdd9b144c01ef2635bbb2fb2c","datavalue":{"value":{"amount":"+0.8185997605323792","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":"Q1658779$779D0D9D-1450-4F8D-BB01-F36964F30C12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7aec8e456eaca575c17c16e4924a3004e4fecf51","datavalue":{"value":{"entity-type":"item","numeric-id":2799604,"id":"Q2799604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a271935cc42a38264c902478f8394f3b0f60ebb3","datavalue":{"value":{"amount":"+0.8167135715484619","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":"Q1658779$11B57486-3832-4450-9C14-19A3CA5BFA84","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Proper distinguishing colorings with few colors for graphs with girth at least 5","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Proper_distinguishing_colorings_with_few_colors_for_graphs_with_girth_at_least_5"}}}}}