{"entities":{"Q640414":{"pageid":642262,"ns":120,"title":"Item:Q640414","lastrevid":63215616,"modified":"2026-04-11T11:23:31Z","type":"item","id":"Q640414","labels":{"en":{"language":"en","value":"List-distinguishing colorings of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5960023"}},"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":"Q640414$3E24CDF3-2582-4E56-9666-7011F8020184","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"de22981991a1474e6f6d06d7ae9d1840e4d00dda","datavalue":{"value":{"text":"List-distinguishing colorings of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q640414$ADBAD38B-A0EF-41A7-A99E-000777A4EA9C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"71515e8a01500ac92f78e85d24b5274101c1176e","datavalue":{"value":"1230.05127","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640414$0693217B-45FB-4EAC-AFCC-19D4138417C8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"db614d934050b7c0db7626164bc4cfb751fef327","datavalue":{"value":{"entity-type":"item","numeric-id":247196,"id":"Q247196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640414$C17F99CD-92FA-4F44-8F37-8CDD870B6E77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e302c703f96a0f15b85a7a84a84d6b5e5365ed96","datavalue":{"value":{"entity-type":"item","numeric-id":181834,"id":"Q181834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640414$C3F7F0FC-5177-43D5-8E28-7FED3988DCBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe77ec2b4526bab176ac013f5e3843618810f783","datavalue":{"value":{"entity-type":"item","numeric-id":1789057,"id":"Q1789057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640414$E969D4C3-38FF-4D2C-A2B9-3027393A0B54","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":"Q640414$6A319183-D48D-4477-AF42-4441ACD3D546","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9767fe8dd1d6f9791ae763e9a67550b5f9aa27e1","datavalue":{"value":{"time":"+2011-10-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q640414$AE8383B8-E28F-4491-B69F-81AF4172678A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"207f441c65ccf8eb3bdbec789cc08cb415b5c6f6","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p161.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q640414$81205293-4E9E-45CF-BF25-0BB6B5CF2DC1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f8dcf11a8a6ec3de55a3af608fa2156735573f1f","datavalue":{"value":"Summary: A coloring of the vertices of a graph \\(G\\) is said to be distinguishing provided that no nontrivial automorphism of \\(G\\) preserves all of the vertex colors. The distinguishing number of \\(G\\), denoted \\(D(G)\\), is the minimum number of colors in a distinguishing coloring of \\(G\\). The distinguishing number, first introduced by Al- bertson and Collins in 1996, has been widely studied and a number of interesting results exist throughout the literature.   In this paper, the notion of distinguishing colorings is extended to that of listdistinguishing colorings. Given a family \\(L = \\{L(v)\\}_{v\\in V(G)}\\) of lists assigning available colors to the vertices of \\(G\\), we say that \\(G\\) is \\(L\\)-distinguishable if there is a distinguishing coloring \\(f\\) of \\(G\\) such that \\(f (v) \\in L(v)\\) for all \\(v\\). The list-distinguishing number of \\(G,\\, D_\\ell (G)\\), is the minimum integer \\(k\\) such that \\(G\\) is \\(L\\)-distinguishable for any assignment \\(L\\) of lists with \\(|L(v)| = k\\) for all \\(v\\). Here, we determine the list-distinguishing number for several families of graphs and highlight a number of distinctions between the problems of distinguishing and list-distinguishing a graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q640414$E0FFAD9C-6D25-4A29-8F90-E622F0E7261C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640414$4E66F096-B4B8-45F3-80A4-7D858E277AB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640414$DADA6E02-DBD9-4FED-822F-93E4D01FAF44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"336ae5fda4ed4c8d62524e5b8cfdb13dfa430cc6","datavalue":{"value":"5960023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640414$189EAEE5-BFED-47F6-8D7E-803EC093E83B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb3e3bb8b0c036a623403117c28f4237a7417347","datavalue":{"value":"distinguishing coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q640414$E2091DCF-B281-44ED-8385-47960A025B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5f6aefdf1ffec3bc08d67d0b64a04330c0d9134","datavalue":{"value":"list coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q640414$998D1B04-4A45-4BFA-AF3E-5E3D8EC6ABF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5e810fc6465a0c1e7299deddf810bab3a7d728a","datavalue":{"value":"list-distinguishing coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q640414$0ED2DB1F-DDF1-4617-BB75-EB25C07FACE2","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":"Q640414$E29CA6D6-8215-43BB-B602-9F5D3CC4ADD2","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c13c685bd25e4998bda78d14b3403b2504a8fc25","datavalue":{"value":"bafkreiaabloex2eogeih42vz7mi7ti3fvad6ljkb5f5zbinytasuqmbdey","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640414$E3FEE3E7-BC28-49F5-8989-9032CE1332FB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad8595111a95758d12c940645003af5255c18449","datavalue":{"value":{"entity-type":"item","numeric-id":1946232,"id":"Q1946232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38ab2bc2519eb3a35a9486fe3807221d1fe2b08f","datavalue":{"value":{"amount":"+0.8967279195785522","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":"Q640414$31402522-376A-4481-A106-CFE687DF10D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25593ac1b8f139790b4b1771719cdcabf8783b80","datavalue":{"value":{"entity-type":"item","numeric-id":503677,"id":"Q503677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0639f3c3dafdeab27e241cc8609e2ff64b707ad","datavalue":{"value":{"amount":"+0.8834949731826782","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":"Q640414$1D88927A-9A65-4D6A-9F9C-0A3711167DD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c89e1f3b30dad36089fc411f67ab8699f4797547","datavalue":{"value":{"entity-type":"item","numeric-id":1693128,"id":"Q1693128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddcd4eea7486250e1d9c634673c3aeb8f760dd02","datavalue":{"value":{"amount":"+0.8667678236961365","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":"Q640414$CC54E79D-6A5C-4138-8B2A-1ED3742E18C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4390642a16cc553a78b3c68478d19fe094367a70","datavalue":{"value":{"entity-type":"item","numeric-id":2421867,"id":"Q2421867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d167805b74b342f57208584f8cbb298ae13d4f9d","datavalue":{"value":{"amount":"+0.8481890559196472","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":"Q640414$B0661AAF-8716-4E4E-A402-874F739D6BCB","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":"a3aab41579fff50ff1022960cbb9fe6c199afd27","datavalue":{"value":{"amount":"+0.845466136932373","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":"Q640414$B45387A4-4A1E-42CB-BFE1-63627AAFAE40","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"List-distinguishing colorings of graphs","badges":[]}}}}}