{"entities":{"Q2048557":{"pageid":2059299,"ns":120,"title":"Item:Q2048557","lastrevid":57479370,"modified":"2026-03-31T02:47:30Z","type":"item","id":"Q2048557","labels":{"en":{"language":"en","value":"On asymmetric colourings of claw-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7379548"}},"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":"Q2048557$091E4A07-195A-4242-829C-5E4FEC4DB9BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7644b27ed052144c9d70b2c2d455450c8b673519","datavalue":{"value":{"text":"On asymmetric colourings of claw-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2048557$6D665A5A-9A04-476B-8133-B4991A605BD1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"57e9d4096cd03589faf215e006e24ad82669d292","datavalue":{"value":"1470.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048557$93CE1515-F431-4232-8297-CF88F909E18C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e7dfb918b2c62f96ef3b1305d9e16ecdae9edca5","datavalue":{"value":"10.37236/8886","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048557$1B313570-D9D7-4985-89C2-9A548878E7C0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"10c07f8b7e3cd9f2923ddf5077d5a80431b6d4ef","datavalue":{"value":{"entity-type":"item","numeric-id":201986,"id":"Q201986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$322FBE48-D60F-49E7-801F-B4667C6452E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6dc8d1cb4395a99ff797b651e9683172712fdc6b","datavalue":{"value":{"entity-type":"item","numeric-id":396836,"id":"Q396836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$751EBE04-F682-4B71-9295-FF98FB641D8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f71a0ce487c9bb2da56554a416a64948e5c3714d","datavalue":{"value":{"entity-type":"item","numeric-id":396837,"id":"Q396837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$F1E8B28D-7F31-4AFA-BDBF-A5AB187F84A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ec776307a493d4b0a32c7ac07b6c2cb715e66f0","datavalue":{"value":{"entity-type":"item","numeric-id":186129,"id":"Q186129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$EFFBF1EB-9F75-4D1F-9164-54DBB237495F","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":"Q2048557$B9024DCA-4DC7-44EB-9158-6A4AB03B1022","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"30e793a417e36fabefb163f4091de1cf887efc65","datavalue":{"value":{"time":"+2021-08-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2048557$A9A847DF-B84F-45A1-A916-AEA008A8B580","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f27eb42f28e2643bfa37b5c82e02e6d669620420","datavalue":{"value":"Summary: A vertex colouring of a graph is asymmetric if it is preserved only by the identity automorphism. The minimum number of colours needed for an asymmetric colouring of a graph \\(G\\) is called the asymmetric colouring number or distinguishing number \\(D(G)\\) of \\(G\\). It is well known that \\(D(G)\\) is closely related to the least number of vertices moved by any non-identity automorphism, the so-called motion \\(m(G)\\) of \\(G\\). Large motion is usually correlated with small \\(D(G)\\). Recently, Babai posed the question whether there exists a function \\(f(d)\\) such that every connected, countable graph \\(G\\) with maximum degree \\(\\Delta(G)\\leqslant d\\) and motion \\(m(G)>f(d)\\) has an asymmetric \\(2\\)-colouring, with at most finitely many exceptions for every degree.  We prove the following result: if \\(G\\) is a connected, countable graph of maximum degree at most 4, without an induced claw \\(K_{1,3}\\), then \\(D(G)= 2\\) whenever \\(m(G)>2\\), with three exceptional small graphs. This answers the question of Babai for \\(d=4\\) in the class of claw-free graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2048557$1C726354-0AEF-4D0F-AFC6-4AF2648050AD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048557$D92069E0-518F-4B7D-AD69-0CB8F6D5DE4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048557$03AA5028-521A-4109-A212-36B17E859615","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e7fc0c749d1c34f9ab0b9217d8d0fbdcb49c8fe7","datavalue":{"value":"7379548","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048557$8F64F03F-DC9F-4AC2-A83A-FE9E38500DC1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e978f705a2acf23757c6789e662b5d1aa514ab62","datavalue":{"value":"asymmetric colouring number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2048557$F7A3F029-2E6D-4675-A0C0-624C724C9C49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f161ce45f2c032a5d05185ff52a7738050ecdea9","datavalue":{"value":"distinguishing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2048557$4D29F560-4036-415D-B166-84FE028E6250","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":"Q2048557$AA91B142-4A58-4468-A832-1C63E403F4CD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d3ef6c77716f803d1477b6d2aeab9ab1c84b8a9c","datavalue":{"value":"https://doi.org/10.37236/8886","type":"string"},"datatype":"url"},"type":"statement","id":"Q2048557$8277A9F2-423C-4BBF-91C3-3533D9654D69","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1501121450339e72e4ef8d627d3ba6e560030349","datavalue":{"value":"W3185033389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048557$1607A95C-2401-4D8A-AA63-F6B7360BD8BD","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":"Q2048557$020F6586-0B90-4BEE-A548-6A6D30EE6C5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6c2fb91865b427eeb2b3ee25fe4492636b364fb","datavalue":{"value":{"entity-type":"item","numeric-id":4597478,"id":"Q4597478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$20104997-9547-4DEB-AA5C-3ACAC3EF1076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"664b49fababc5bd3247ee4ab3f417edd5363ec4f","datavalue":{"value":{"entity-type":"item","numeric-id":1082430,"id":"Q1082430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$068B0C12-6ED8-4238-92EF-23E2B8106D31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd3013a8440a053c1a824fba68ad72f7bc668730","datavalue":{"value":{"entity-type":"item","numeric-id":396886,"id":"Q396886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$26ECF1EA-3289-4BC4-80A1-D7889D6FCD19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c134a8237b761e0b50b763f08ce155caaf906e3a","datavalue":{"value":{"entity-type":"item","numeric-id":2278113,"id":"Q2278113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$32029A25-4DC8-4193-97BA-7DC4972E9EDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d8867b3bc750c1e33cded1224f80955c9deb7b5","datavalue":{"value":{"entity-type":"item","numeric-id":2372880,"id":"Q2372880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$C627EA72-4F06-470D-9328-74D180654DCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b7db251371378652f865204eee6987b3f80afed","datavalue":{"value":{"entity-type":"item","numeric-id":2189429,"id":"Q2189429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$4C9C7ED6-8D8D-45BD-A4E4-AB7D6C508AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc60356d792150b3e508cf915ac0cd58348ed2ab","datavalue":{"value":{"entity-type":"item","numeric-id":2522665,"id":"Q2522665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$DBB9E7F2-D371-4CAD-AEA8-1BB87EB2B410","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":"Q2048557$E21BE99E-0A5B-413C-8C2F-1A1DD34CE5CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e7854cbc53e4776d4a10e431ca1697213ce96d2","datavalue":{"value":{"entity-type":"item","numeric-id":2509274,"id":"Q2509274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$1BD4390C-57C6-4703-8376-7B2F2AE1688D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac09954b908b05cb23d1329ebdfe9cf59aa5c21f","datavalue":{"value":{"entity-type":"item","numeric-id":2407385,"id":"Q2407385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$6F64B57A-9891-4789-AB5A-508E4DC76D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60936987a4a91c606a5c6b9925f2aa716c6eae2a","datavalue":{"value":{"entity-type":"item","numeric-id":776279,"id":"Q776279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$ABDF2A09-41E5-4348-BC16-4916E03FAD4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20c152e2fc02c2192aecf489000f80a2f469df2d","datavalue":{"value":{"entity-type":"item","numeric-id":4993953,"id":"Q4993953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$7DB98E85-F4EF-4F00-B2D4-CF92C3B38B29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d385d69ece430ba2d8225024ab534fe521a91cd7","datavalue":{"value":{"entity-type":"item","numeric-id":4604514,"id":"Q4604514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$3E315718-E5CD-4FF1-A116-6D5509B8B308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad787c47f4b70acf95b9a1285e3ebcb60fc2994d","datavalue":{"value":{"entity-type":"item","numeric-id":5110667,"id":"Q5110667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$1A7563AC-7096-4726-8FF4-73923E602192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21a2718643947727b4637bd5ccdce261b67b5511","datavalue":{"value":{"entity-type":"item","numeric-id":1385847,"id":"Q1385847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$53F8DB60-33CA-4B2F-A30D-C91CE02959AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bb7bbe8743dfedf8c72f40d38e154ca446bfe2","datavalue":{"value":{"entity-type":"item","numeric-id":540028,"id":"Q540028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2048557$74EFC5EC-68D7-436A-86E0-B03FE51F0E38","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"8cbf9c53fc2af8e4ca81902b656ad028098ed2ee","datavalue":{"value":"bafkreiggxajf4hgdjlye6krbcvwzct5g4q4ytgvbfcc2p72iqd6pivp7ea","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2048557$358B76F2-F93E-4C0C-88D0-D3A1D824DAE1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f0ac8f6982ba9568d124e221b223b4ac1d78569","datavalue":{"value":{"entity-type":"item","numeric-id":2189429,"id":"Q2189429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b3ad5cbe98f50fd87468392da30c50f3d52e79a","datavalue":{"value":{"amount":"+0.7793084979057312","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":"Q2048557$B3A8863C-5B5F-4725-A443-B9061D23F15B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e4871cf8a71b3a47a4d335d639a51e7f7addcb6","datavalue":{"value":{"entity-type":"item","numeric-id":2407385,"id":"Q2407385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51ae3a1219f22003806dc7c7715a313d05e1cef8","datavalue":{"value":{"amount":"+0.7720438838005066","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":"Q2048557$D659CAED-FB1B-4187-BAFD-6735FEA3D00F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f61f326e679ea6c561341f42fbfadf3da0bac25","datavalue":{"value":{"entity-type":"item","numeric-id":2674556,"id":"Q2674556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9396d94b829cd6b4343159209762fd692cd2afb","datavalue":{"value":{"amount":"+0.7714189887046814","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":"Q2048557$B1EF274E-C1C8-4452-B1C7-2C7AC6FC4679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89869053ab25bd3073efadfb369cc3415c9435a3","datavalue":{"value":{"entity-type":"item","numeric-id":2363696,"id":"Q2363696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba3ac8d0bb3aecdc1732fc03cd64e8a9b77486dc","datavalue":{"value":{"amount":"+0.7698027491569519","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":"Q2048557$487A2A91-A1CE-49AB-ACAE-B12CD1CA7721","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d931aa49044b9ba92fc1cdc94b784c6e2d7842e9","datavalue":{"value":{"entity-type":"item","numeric-id":6081887,"id":"Q6081887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19d0c2e5313d45a59af06c0ec7db0e87741c0444","datavalue":{"value":{"amount":"+0.7687307000160217","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":"Q2048557$8DB530D7-5F85-43D4-8BEE-BAAF04B22B05","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":"Q2048557$0420486B-B3DE-4B2E-B338-F55F3FC0F421","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2048557","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2048557"}}}}}