{"entities":{"Q1953404":{"pageid":1964146,"ns":120,"title":"Item:Q1953404","lastrevid":51733988,"modified":"2026-01-19T18:10:39Z","type":"item","id":"Q1953404","labels":{"en":{"language":"en","value":"The distinguishing chromatic number of Kneser graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6171862"}},"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":"Q1953404$00EE73DF-EF84-48E3-AA45-D41854E18246","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"af0be076a6560344b55de0fd254edb6059afb4d0","datavalue":{"value":{"text":"The distinguishing chromatic number of Kneser graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1953404$34ECD7BD-346D-4B8B-830D-1E35977D9EF9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"00876df38620755767867a2f0dca071fbf1d8e1c","datavalue":{"value":"1266.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953404$BA0BC9B2-E914-43C5-BC32-17029E9890D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c9d632c5c15667594e39c4732b26686d5baac95","datavalue":{"value":{"entity-type":"item","numeric-id":712260,"id":"Q712260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953404$ACFCA669-1FAF-41FC-82D5-A5F7EA1BD691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a80f0a30c34568b1594b2aaace08fe6b51a1e6b","datavalue":{"value":{"entity-type":"item","numeric-id":234314,"id":"Q234314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953404$BF4418B9-7EC2-4BE8-A37D-50DF3C783EBE","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":"Q1953404$02B6B3D9-FCEF-4419-B073-036D11788520","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4a8303ee696998ba030c9b1c3b6bc07c6038c334","datavalue":{"value":{"time":"+2013-06-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":"Q1953404$D485BC0D-01E7-4EA0-AA56-335587AA5FAE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"034d5b77077c0e74a2e1a5deaacc82a475352341","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p23","type":"string"},"datatype":"url"},"type":"statement","id":"Q1953404$4E3E7370-3D7A-4BDA-8D23-9794C750E8C9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bcf0de0d55a7a71b29e77e0c253831468a9e2afc","datavalue":{"value":"Summary: A labeling \\(f: V(G) \\rightarrow \\{1, 2, \\ldots, d\\}\\) of the vertex set of a graph \\(G\\) is said to be proper \\(d\\)-distinguishing if it is a proper coloring of \\(G\\) and any nontrivial automorphism of \\(G\\) maps at least one vertex to a vertex with a different label. The distinguishing chromatic number of \\(G\\), denoted by \\(\\chi_D(G)\\), is the minimum \\(d\\) such that \\(G\\) has a proper \\(d\\)-distinguishing labeling. Let \\(\\chi(G)\\) be the chromatic number of \\(G\\) and \\(D(G)\\) be the distinguishing number of \\(G\\). Clearly, \\(\\chi_D(G) \\geq \\chi(G)\\) and \\(\\chi_D(G) \\geq D(G)\\).    \\textit{K. L. Collins} et al. [ibid. 16, No. 1, Research Paper R88, 14 p. (2009; Zbl 1186.05051)] have given a tight upper bound on \\(\\chi_D(G)-\\chi(G)\\) in terms of the order of the automorphism group of \\(G\\), improved when the automorphism group of \\(G\\) is a finite abelian group. The Kneser graph \\(K(n,r)\\) is a graph whose vertices are the \\(r\\)-subsets of an \\(n\\) element set, and two vertices of \\(K(n,r)\\) are adjacent if their corresponding two \\(r\\)-subsets are disjoint.    In this paper, we provide a class of graphs \\(G\\), namely Kneser graphs \\(K(n,r)\\), whose automorphism group is the symmetric group, \\(S_n\\), such that \\(\\chi_D(G) - \\chi(G) \\leq 1\\). In particular, we prove that \\(\\chi_D(K(n,2))=\\chi(K(n,2))+1\\) for \\(n\\geq 5\\). In addition, we show that \\(\\chi_D(K(n,r))=\\chi(K(n,r))\\) for \\(n \\geq 2r+1\\) and \\(r\\geq 3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953404$626C7B0C-8FE2-4DEA-955F-8BA8EF8A97FA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953404$001306FD-9911-440F-B1F2-A4414EC1517D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953404$064902F6-C8AF-40E7-99C4-472C78870281","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d6b37653ceaf56984332bbf9233a0a5c74baf639","datavalue":{"value":"6171862","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953404$4F18B4D1-5B05-4944-A24C-87A4582E5358","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f161ce45f2c032a5d05185ff52a7738050ecdea9","datavalue":{"value":"distinguishing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953404$F7BF82A8-49A9-47B8-9DD2-1D1EA06C0B3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a59ba2750774c4fe5438f914dd85e56cf4c0b57","datavalue":{"value":"proper coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953404$32E4AED0-EC10-420B-A2DB-014B8737EE07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c0140de3f08eb78ec7999a29727e9d8a4f3a187","datavalue":{"value":"distinguishing chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953404$58E14AD4-D629-4532-821C-7C3C16B0FD4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7fff5a0ac93eaaa52c6433bfb30dda7c93a583e","datavalue":{"value":"Kneser graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953404$2744F78E-0069-4220-967B-4B2DD020DF7F","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":"Q1953404$BD54DDC3-34E4-46E1-8181-538B7768ACF2","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"456efec57af1b4d2b1e04447f559419b2075e32e","datavalue":{"value":"bafkreifargphdxufqaphrttfwv2hb4z7uapw5xhyfnqsu4vsdd7q6ugeim","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953404$53E20D8D-740A-494A-AE62-EFAB0B21685B","rank":"normal"}],"P1643":[{"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":"f92e794ebeccaa887e1cee170b3b7a630d7468e2","datavalue":{"value":{"amount":"+0.8737491965293884","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":"Q1953404$52B42555-F1F8-4FC7-8912-46A41E1FF421","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"805f97f44020587d5bdad2ac1ba6b0fa6707f51c","datavalue":{"value":{"entity-type":"item","numeric-id":870080,"id":"Q870080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6d78d1716144c60c9e825f5d14b92bfdb7d9a2f","datavalue":{"value":{"amount":"+0.8729557991027832","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":"Q1953404$D55509B4-0D99-444F-99BF-A646630D4311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a865c4ac82b542aef5287fe3b4800a04f99bc1c3","datavalue":{"value":{"entity-type":"item","numeric-id":5405510,"id":"Q5405510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"673eef61cefe6ec5cae59557ca936dd10576977f","datavalue":{"value":{"amount":"+0.8424058556556702","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":"Q1953404$8A5E6F46-F02D-4687-AD9B-21A6D30CDB3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f2e0936dd683d70da97e6d1b3e9b73c9085f139","datavalue":{"value":{"entity-type":"item","numeric-id":5217075,"id":"Q5217075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb71868df0e6c8c111a655a9f41a2805a5eeb25a","datavalue":{"value":{"amount":"+0.8242159485816956","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":"Q1953404$6E945C23-93DA-4EE0-BF1B-2265C5285C10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ff6cac5c6ea5a1e4a7921c4da54929406af2a76","datavalue":{"value":{"entity-type":"item","numeric-id":2380243,"id":"Q2380243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"740c466478f51b65166323d47a46c97b8b77fe77","datavalue":{"value":{"amount":"+0.8234657645225525","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":"Q1953404$341BAD3D-49CA-40C5-921E-6F776DEEBF94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1953404","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1953404"}}}}}