{"entities":{"Q2363696":{"pageid":2374439,"ns":120,"title":"Item:Q2363696","lastrevid":72607758,"modified":"2026-04-14T06:03:21Z","type":"item","id":"Q2363696","labels":{"en":{"language":"en","value":"Bounds for distinguishing invariants of infinite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6752056"}},"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":"Q2363696$71F511D3-5370-484E-A55B-0C1F24160885","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"be193c8a874b1c6d6cb8443eab4f74ef15904f8a","datavalue":{"value":{"text":"Bounds for distinguishing invariants of infinite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2363696$324B5735-AA6F-46C3-A9C6-45CC7D237C43","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f08208a1ce1b79b4835406105f4a4d94151af961","datavalue":{"value":"1368.05051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363696$A219738E-868A-470E-A040-6EC344542D55","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":"Q2363696$A1B45350-34E2-4026-AF30-311BF80F6105","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":"Q2363696$892B23CE-C1EC-4CA5-9871-B6B519DD5C82","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":"Q2363696$77A8DC38-039A-45CF-B428-07C07634BDD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7ba121b5baeda07fdbbffe156dde0ef2df9b677c","datavalue":{"value":{"entity-type":"item","numeric-id":776311,"id":"Q776311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363696$95932000-3207-44C3-B984-42EA6D168FBF","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":"Q2363696$58D1996B-E3A3-49ED-A349-CA38E0AA86C2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"88acc2f980fa4865c29a618cd3ee152842fc9da9","datavalue":{"value":{"time":"+2017-07-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":"Q2363696$55AB9EEB-3908-49C4-A333-107504A2B282","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c11ec69dfcc302b585e1b133cfd2351bb1ae7fdd","datavalue":{"value":"https://arxiv.org/abs/1910.12107","type":"string"},"datatype":"url"},"type":"statement","id":"Q2363696$447816ED-09A0-45E4-B6B3-A7FC2BE52257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"89c110411552efcda0d60e627f55e56323b7279f","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p6","type":"string"},"datatype":"url"},"type":"statement","id":"Q2363696$7A470C60-CED8-484D-A107-2DFF26DDB235","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8239f296119ed8fd431edf8d80b00b8d0e8821fa","datavalue":{"value":"Summary: We consider infinite graphs. The distinguishing number \\(D(G)\\) of a graph \\(G\\) is the minimum number of colours in a vertex colouring of \\(G\\) that is preserved only by the trivial automorphism. An analogous invariant for edge colourings is called the distinguishing index, denoted by \\(D'(G)\\). We prove that \\(D'(G)\\leq D(G)+1\\). For proper colourings, we study relevant invariants called the distinguishing chromatic number \\(\\chi_D(G)\\), and the distinguishing chromatic index \\(\\chi'_D(G)\\), for vertex and edge colourings, respectively. We show that \\(\\chi_D(G)\\leq 2\\Delta(G)-1\\) for graphs with a finite maximum degree \\(\\Delta(G)\\), and we obtain substantially lower bounds for some classes of graphs with infinite motion. We also show that \\(\\chi'_D(G)\\leq \\chi'(G)+1\\), where \\(\\chi'(G)\\) is the chromatic index of \\(G\\), and we prove a similar result \\(\\chi''_D(G)\\leq \\chi''(G)+1\\) for proper total colourings. A number of conjectures are formulated.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363696$91D0112F-7BE2-4EC5-9597-3B21AD166A74","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363696$F951211F-F6D0-4479-B84C-D992B73E2706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363696$8231E3C6-1E35-4B6B-AA26-473112382577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9729428b7f3faff6f70db9a7fa765e75946ff6b6","datavalue":{"value":"05C63","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363696$EA8CCB59-4889-4029-91AF-A347BD70370A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b70040cf072d8bf34e80d9b371147c372810113a","datavalue":{"value":"6752056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363696$1B7D5FD8-12A4-4762-8682-09184DA1CB37","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"721db152ea6f5f1d941a96190ff027c3df9b3519","datavalue":{"value":"symmetry breaking","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363696$46A32F7B-9005-4E8D-8664-F7D831E37E95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"514ab5591ba68dc7c232f333f43d53ffafb22363","datavalue":{"value":"distinguishing colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363696$7AF1E300-0C50-4420-A115-7C285981BFD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"353f405eab80341536e77430c0cc4488317bee19","datavalue":{"value":"infinite motion conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363696$7AD782E2-23DE-4B48-9779-3F35C9E81F44","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":"Q2363696$D28994AC-7EB4-4F24-9D24-1AC50254A29A","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":"Q2363696$6BF67533-DC25-4BCE-ABA8-8125F8FDBB1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e6a4d7a959d3b18940b02631c167661356b3481","datavalue":{"value":{"entity-type":"item","numeric-id":1212469,"id":"Q1212469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363696$5D7D14C5-2787-49DE-8999-B6DF79A0C328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae6a5a1fe6fcc2b45c8fdda2f7ef8ee4811adc06","datavalue":{"value":{"entity-type":"item","numeric-id":2341071,"id":"Q2341071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363696$BA1A79CD-A6E6-4EEC-8E5C-264AB70387A5","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":"Q2363696$060C23C5-5B3C-477D-B79B-6CA16D7B4120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62e967816953cecad41268e715794a55d56323d","datavalue":{"value":{"entity-type":"item","numeric-id":3577833,"id":"Q3577833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363696$930E0C77-8B19-48D9-A621-E94717B005F5","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":"Q2363696$2F74980B-1AE0-4965-BC93-809D5541FA4E","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":"Q2363696$11A6CDCC-EE7C-4C2C-B0CA-F41E5DD91309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bff21bf714923e7891563bddf0604c2b3d359c4","datavalue":{"value":{"entity-type":"item","numeric-id":2835392,"id":"Q2835392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363696$D207A5C0-33B5-4E4D-B3A2-A797F79927AA","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":"Q2363696$6A80E1F6-E308-4F89-933A-ECD8D6832EA7","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":"Q2363696$08634697-E851-42A4-9BB7-42AEFABCD90D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3059b9386f802d26103ef0fe34232b57cefa08d9","datavalue":{"value":{"entity-type":"item","numeric-id":888634,"id":"Q888634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363696$4045A961-DC9B-4B03-9F4B-75B3DF44249E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20c169388e4dfaaff7e4c7279d06b128f6581166","datavalue":{"value":{"entity-type":"item","numeric-id":1331970,"id":"Q1331970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363696$0DE97126-C82C-4C2B-B236-496855D0A9BA","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":"Q2363696$11DDDC75-33E3-418A-BFAD-7C421C8A63D5","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":"Q2363696$5C52D40C-8521-4A52-B1C1-790474E60464","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"255f3e3246d82b32f184f1d7c7fea4cc61e71e92","datavalue":{"value":"bafkreidilntipgxoyg6qb6y2t4uszkjlkfj4agsqctaxvqnu7bf225twcm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363696$B63230E4-F97E-4581-A88C-AFFA996AB879","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"175c2d3a9d410ddeea3a596c48f2d5fbaf6cde87","datavalue":{"value":{"entity-type":"item","numeric-id":2341071,"id":"Q2341071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf201e6a35609cf98cb31f04b94011e4b1376fa9","datavalue":{"value":{"amount":"+0.9160897731781006","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":"Q2363696$6B988AC5-DB5E-4DEA-8003-A2E005974656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34baaf730b9106db7e19231d2688372e3d8132ba","datavalue":{"value":{"entity-type":"item","numeric-id":5110667,"id":"Q5110667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d5dfd263e58aecb2f4663d75efeccb087a2495f","datavalue":{"value":{"amount":"+0.8857800960540771","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":"Q2363696$71449303-6A99-4775-BB81-59A3006BB654","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":"e69bfee9167e0b7bc9521436f2f1517537410359","datavalue":{"value":{"amount":"+0.8829089403152466","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":"Q2363696$9FADB652-46F6-4C3D-9E79-9C84047F9CD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e891431a2c48dbdf04ecb1922a62daf86511ef78","datavalue":{"value":{"entity-type":"item","numeric-id":2198979,"id":"Q2198979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ccb290780a0950e29bf00fa8325b8c1687594c7","datavalue":{"value":{"amount":"+0.868321418762207","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":"Q2363696$AD1D570D-7548-48B1-B066-0CBB2CA85D38","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":"cd469bb6a1dbe7c2666cf2fe086339e58841363e","datavalue":{"value":{"amount":"+0.8669925332069397","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":"Q2363696$FBF701E2-E66E-4576-ACC9-CE7743B80D30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounds for distinguishing invariants of infinite graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounds_for_distinguishing_invariants_of_infinite_graphs"}}}}}