{"entities":{"Q785585":{"pageid":787434,"ns":120,"title":"Item:Q785585","lastrevid":64319607,"modified":"2026-04-11T19:03:37Z","type":"item","id":"Q785585","labels":{"en":{"language":"en","value":"Edge-distinguishing of star-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7229464"}},"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":"Q785585$DDEE5F12-F491-4C01-AA54-193EDD60D6FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7c9805453fe2a801bb69a251d7e942fd312c32b3","datavalue":{"value":{"text":"Edge-distinguishing of star-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q785585$334E28B2-1530-4C2C-B486-59CCE8DB7FF1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6036fc5cb9200eee3bf3fbc3185074a056101581","datavalue":{"value":"1445.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q785585$86065D41-C3E4-449F-AC4B-039283259910","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b96d2ee004f830ae20e60a146c08e94e48dcdbe9","datavalue":{"value":"10.37236/8882","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q785585$30F2D73E-C20A-4988-8B7E-3A606D12C25E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ce33a91b9f06699fbe67f71c5248a4faa32e796","datavalue":{"value":{"entity-type":"item","numeric-id":785581,"id":"Q785581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q785585$9FABC046-E8A4-463A-A261-922BF385A8BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e6b4969c6e77fa85c04ecd2e2be10dffc178868","datavalue":{"value":{"entity-type":"item","numeric-id":785582,"id":"Q785582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q785585$35B10D98-A38D-460A-B61D-C63598D5BEE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"55c432d3fcdf7aaa04c32e8eabe13013b73ad787","datavalue":{"value":{"entity-type":"item","numeric-id":785583,"id":"Q785583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q785585$C3ADD85A-57CB-4688-AB03-90A636CAA90A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e02f2648fc1cc7de92446b57995d41e6f2bdb86b","datavalue":{"value":{"entity-type":"item","numeric-id":785584,"id":"Q785584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q785585$89FF9248-A1EF-43DD-B4F6-CD47F7A58D72","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":"Q785585$C452EEAB-3D92-48DA-B18A-4921CFD94143","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5455c1d81d4a01ed39f1551e0dc8701e3aa1c562","datavalue":{"value":{"time":"+2020-08-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q785585$7A172339-A085-420F-8276-1D3B3768DA54","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9966b1de54272899f97a4da272d4dc79c17004af","datavalue":{"value":"Summary: The distinguishing index \\(D^\\prime(G)\\) of a graph \\(G\\) is the least number \\(k\\) such that \\(G\\) has an edge colouring with \\(k\\) colours that is only preserved by the trivial automorphism. \\textit{M. Pil\u015bniak} [Ars Math. Contemp. 13, No. 2, 259--274 (2017; Zbl 1380.05028)] proved that a connected, claw-free graph has the distingushing index at most three. In this paper, we show that the distingushing index of a connected, claw-free graph with at least six vertices is bounded from above by two. We also consider more general graphs in this sense. Namely, we prove that if \\(G\\) is a connected, \\(K_{1,s}\\)-free graph of order at least six, then \\(D'(G) \\leqslant s-1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q785585$BE6B9D58-FF68-4B14-9866-A9FEDF00C605","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q785585$445259EB-6C6F-49A8-BBC7-259BA3DD6DAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q785585$A64811E8-22A4-43FB-9443-A6B39FAF1F0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q785585$2B7907F9-40FC-4E07-84C7-BFB49A6C79F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q785585$CF950D82-CACA-4CE9-9B9E-94F582CE05F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7ae77b7014ae74d050ddd08c7570cbea14e17b7f","datavalue":{"value":"03E10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q785585$16FE4C10-FCE2-4E31-AF86-07142E7DD596","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b6602b25c60afd2133a65b79a900c3b2e72b0d3a","datavalue":{"value":"7229464","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q785585$B1F88EDD-B1AA-4D8D-8DBF-EEDD5DB7F0DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e3d58b5f68ae7d6337620e7d25da0081273ed23","datavalue":{"value":"edge colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q785585$23D3EB3E-2479-4DD3-8D4B-7A5604B2F461","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"45fa8cd850059f9df27eba7c2cdbc079cd98a28b","datavalue":{"value":"symmetry breaking in graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q785585$7A19ABC7-4FE8-41AB-AFA6-27C9404AC89A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a78ae59ab9d8190885e58519a4684cf477e0cb0","datavalue":{"value":"distinguishing index","type":"string"},"datatype":"string"},"type":"statement","id":"Q785585$FCBA88D9-6FC3-477A-805E-6908F1DBA55D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef67640bec3c4afe93760825b64ba61c05b28a68","datavalue":{"value":"claw-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q785585$96366B35-BACD-4391-9A31-D8AC660CF014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q785585$54B9A980-6031-4488-AFFD-52D97B863D02","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":"Q785585$0ED789BA-B4AF-4435-BDD4-E471FDAFCFCC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ba468f98746439aeff773b2271915545c3f31957","datavalue":{"value":"https://doi.org/10.37236/8882","type":"string"},"datatype":"url"},"type":"statement","id":"Q785585$96B3AFE9-6CC0-464A-A01F-EEDFAE8F6F8A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3a72afe152c04c96c8e64e21a61066d8e065db5e","datavalue":{"value":"W3081717843","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q785585$4109E900-965B-4007-85FE-C75B8505E7A1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9234f0e63bf5a06d1fb5cac8ee4d51f04190a4c4","datavalue":{"value":{"entity-type":"item","numeric-id":1918875,"id":"Q1918875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q785585$614D2520-BEA9-4493-B60E-E210BC69ED84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"650620a8abff65a78f27b6d9c816323baf828dab","datavalue":{"value":{"entity-type":"item","numeric-id":2829286,"id":"Q2829286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q785585$FB939576-994F-459A-933B-46F46C460B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fcb9d125fa60a766d6a8330d086d9b2f47c0254","datavalue":{"value":{"entity-type":"item","numeric-id":1356695,"id":"Q1356695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q785585$8B5F0206-63F0-41D5-99BE-6B2D1429E789","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a39f3da2fcaeb87a8723684c45b345566273e4b4","datavalue":{"value":{"entity-type":"item","numeric-id":1321993,"id":"Q1321993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q785585$9740A1EB-D80D-4792-BBF1-2717A860AE63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ab679237b5073bba8935cd2c503a9cac44acdb8","datavalue":{"value":{"entity-type":"item","numeric-id":482130,"id":"Q482130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q785585$72C2AB3B-51A2-413B-9C45-FADE8D74CCCD","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"cb003be5f2f2e6e77afac7a8a41f8f7649a6bede","datavalue":{"value":"bafkreicprbq6svudc6e6mvde7z6fqbca3eaw4etpe6wm4z6rkymx72brta","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q785585$9C29AD14-F0D7-4F50-81EA-61127093E884","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7fffe7525401b4acee3b375fcd2f10dda262b88","datavalue":{"value":{"entity-type":"item","numeric-id":4604514,"id":"Q4604514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c6a1dda4d5994ff642a5b0708251d2ef8df4a47","datavalue":{"value":{"amount":"+0.8617041707038879","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":"Q785585$E251A1CB-6FF8-49CC-897C-A9F333D5F096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c0a4b01738cac5392083e852f089b0d24f91153","datavalue":{"value":{"entity-type":"item","numeric-id":482130,"id":"Q482130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b7ec996150724067de79b6b5c1244d6352d3a3d","datavalue":{"value":{"amount":"+0.855855405330658","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":"Q785585$1E21A71F-3F4F-489F-A967-C9D4E1915808","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e27a8926c8d6d2f72b0f358f764c15970b1541ee","datavalue":{"value":{"entity-type":"item","numeric-id":4988841,"id":"Q4988841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"220ddcefb0906755acfd88d0d282e7ed03116c03","datavalue":{"value":{"amount":"+0.852733850479126","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":"Q785585$A1855F2C-7616-4A9C-8A06-621D248EF29C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d39035ad6b05730ba6dac054a4eb64358bfc20db","datavalue":{"value":{"entity-type":"item","numeric-id":4969593,"id":"Q4969593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cb492ff5d07476dd9f92de750f60faea5937135","datavalue":{"value":{"amount":"+0.8511205315589905","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":"Q785585$3314B9E7-B92E-4C2A-917A-F049D54F7D3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a16b00253812852d3d7e8ef5a99bcf6e974e64b","datavalue":{"value":{"entity-type":"item","numeric-id":2142642,"id":"Q2142642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b8efbd72cd7cc0ed925a248e1c163fa433a8460","datavalue":{"value":{"amount":"+0.8235869407653809","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":"Q785585$6001AC54-E7BB-4793-A73C-B5B98155CE1D","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q785585$BB925D0F-0914-4844-8778-9A1C8B672EEB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Edge-distinguishing of star-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Edge-distinguishing_of_star-free_graphs"}}}}}