{"entities":{"Q5894920":{"pageid":7933993,"ns":120,"title":"Item:Q5894920","lastrevid":101878499,"modified":"2026-06-06T03:03:33Z","type":"item","id":"Q5894920","labels":{"en":{"language":"en","value":"Circular chromatic number and Mycielski graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2133894"}},"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":"Q5894920$E746930B-949B-431E-A979-A209DD401638","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"913b1c2f8730f85d5fb6522ed3758ce5a1e7470e","datavalue":{"value":{"text":"Circular chromatic number and Mycielski graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5894920$1CD019F3-3A98-49FD-ACE8-7E73A3441818","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"580580061755f069f0b453fb155f320fcc0c3d57","datavalue":{"value":"1056.05057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894920$E7287028-1ACD-45D6-B857-9FB610249304","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894920$CB49BE0A-BD90-4A77-BFA0-41A55D3CDC9F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e25cede1ef8d2406793b84eb9dd56b013bc7d13f","datavalue":{"value":{"time":"+2005-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5894920$1CE7D73E-8F9E-47A3-860B-8C6CC5879BA8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9f75790658ea2bd6017611528c8aab5884bcc98b","datavalue":{"value":"Given positive integers \\(k,d,\\;k \\geq 2d\\), a \\((k,d)\\)-coloring of a graph \\(G\\) is a mapping \\(c:\\;V(G) \\to \\{0,1,\\dots, k-1\\}\\) such that for each edge \\(xy \\in E(G)\\), \\(d \\leq | c(x) - c(y)| \\leq k-d\\). The star chromatic number is defined as \\(\\chi^*(G) = \\inf\\{\\frac{k}{d}: G\\text{ has a }(k,d)\\)-coloring\\}, see \\textit{A. Vince} [J. Graph Theory 12, No. 4, 551--559 (1988; Zbl 0658.05028)]; this invariant is the same as the circular chromatic number \\(\\chi_c(G)\\) introduced by \\textit{X. Zhu} [J. Graph Theory 16, No. 6, 557--569 (1992; Zbl 0766.05033)].  In the first part of the paper under review, it is shown that if the complement of \\(G\\) is non-Hamiltonian, then \\(\\chi_c(G) = \\chi(G)\\); further, for an \\(n\\)-vertex graph \\(G\\), if there is a set \\(S=\\{a,b,c\\} \\subseteq V(G)\\) such that \\(N(S) \\cup S \\neq V(G)\\) and \\(\\deg(a) + \\deg(b) + \\deg(c) \\geq 3(n-3)\\), then \\(\\chi_c(G) = \\chi(G)\\).   The second part deals with Mycielski graphs (the Mycielski graph \\(M(G)\\) of a graph \\(G\\) is obtained from \\(G\\) by adding \\(n+1\\) new vertices \\(x_1',x_2',\\dots,x_n',u\\) such that each \\(x_i',i=1,\\dots,n\\) is joined to the neighbours of \\(x_i\\) and to \\(u\\); the iterated Mycielski graph is defined recursively by \\(M^m(G) = M(M^{m-1}(G))\\)). The author proves that, for an \\(n\\)-vertex graph \\(G\\), if \\(\\chi(G) \\geq \\frac{n+3}{2}\\), then \\(\\chi_c(M(G)) = \\chi(M(G))\\). Moreover, it is proved that if there are at least three vertices of degree \\(n-1\\) in \\(G\\), then \\(\\chi_c(M(G)) = \\chi(M(G))\\), and if there are at least five such vertices, then \\(\\chi_c(M^2(G)) = \\chi(M^2(G))\\). This implies the known results of \\textit{G. J. Chang, L. Huang} and \\textit{X. Zhu} [Discrete Math. 205, No. 1--3, 23--37 (1999; Zbl 0941.05026)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q5894920$FEADA71A-EA44-4F2C-BD77-21A9D12CCD47","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf552a6496a70699f2802e7f7eff6309238b43f4","datavalue":{"value":{"entity-type":"item","numeric-id":383766,"id":"Q383766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894920$2A414D3F-0496-4657-9B7E-E9FBFCC27D97","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894920$2DFC3EE9-FFB4-4097-B1CF-115E5583DFB1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d4cc7dbc290b6e9d3ecfa6a2cc70a8a392a260bb","datavalue":{"value":"2133894","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894920$3E08F798-B7B3-4146-8290-3A9AE19F2088","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5894920$C8BA0079-D2AD-4CD4-AB0C-30A795E093A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f371dc0947f5d12eb6074ef5ec2c5635c30ee7b2","datavalue":{"value":"Mycielski graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5894920$68EC1866-BC4A-49BE-A957-0E72DF76526E","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":"Q5894920$08C3F48B-C770-4732-8F60-1602ECD03AFD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9d02bc8bf47d9b80f25e7d47d5a0d82ef08bb557","datavalue":{"value":"https://doi.org/10.1007/s00493-004-0008-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q5894920$53ED11A5-0457-4BBD-A052-D13AB24A6CCA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bf8931936942bdc8b75350993cd2f59f68ead6c8","datavalue":{"value":"W2047439437","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894920$FD948A01-EBA4-462D-9788-14BF590F952E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8f78df41236f02e311f475dc27e0eaf0e67e0865","datavalue":{"value":"10.1007/S00493-004-0008-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894920$1091481B-BC07-496A-831D-C36905CF6CCC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0810350ce1832038f11d3f3fc4b1f635ffc25c61","datavalue":{"value":{"entity-type":"item","numeric-id":1877680,"id":"Q1877680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da837f193c0aa549708465c352f9646b35a85997","datavalue":{"value":{"amount":"+0.920948","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5894920$F1F958CD-5359-472B-94AD-9A04ECA296F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41cd6eb0742f1a87636aeea187cabe8a24308a8b","datavalue":{"value":{"entity-type":"item","numeric-id":4432770,"id":"Q4432770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b51548c8e50a91efe66b8aa48c340700962d304","datavalue":{"value":{"amount":"+0.87188286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5894920$9380E85A-4405-4F2E-A8A9-F22F07D1D448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a60f519e0a99301d8da37c810e382d2ec123130d","datavalue":{"value":{"entity-type":"item","numeric-id":3428992,"id":"Q3428992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78d87b4626a70c2ce3926774f30f604d4b9070e4","datavalue":{"value":{"amount":"+0.8390993","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5894920$609BADA2-6914-4EAD-88C4-E071295D866D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b239ff0afae15f93f84868082aa6b6bcb5293d38","datavalue":{"value":{"entity-type":"item","numeric-id":4016022,"id":"Q4016022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bb38b8f4816d137a273ca76f3c4b3497b5be714","datavalue":{"value":{"amount":"+0.8312912","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5894920$8D285FD8-86CE-423E-8DFC-EE7437134D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3371c847f03afe4719d861ec1cc3e99db80b7ab2","datavalue":{"value":{"entity-type":"item","numeric-id":4432769,"id":"Q4432769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82ab2dcae89469561e92d7f79893bb386ab8361f","datavalue":{"value":{"amount":"+0.8288839","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5894920$4333E087-E5A6-4948-BF9F-E12FB7265929","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"727539d77222792c800784f12f155b3c962ef85e","datavalue":{"value":{"entity-type":"item","numeric-id":4736226,"id":"Q4736226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f56e0955b767b788ae5e2ed868e3fbc314974f4","datavalue":{"value":{"amount":"+0.8281094","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5894920$CC740E63-0B5D-4A7C-B533-A2470E8CE8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f5b946a7a81a3fc918010e1f94dc4d9d310251c","datavalue":{"value":{"entity-type":"item","numeric-id":5920576,"id":"Q5920576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ac392a49632bee85b093d26773d4fd5ffa5c9bf","datavalue":{"value":{"amount":"+0.8278156","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5894920$E2E4B666-4A00-4542-8636-F1FE5CAD52C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66fd8629a347be53233c5b9d699e21ffeb8a1180","datavalue":{"value":{"entity-type":"item","numeric-id":2723478,"id":"Q2723478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36184ed4e3c6ebe80345642f9213a3fd09a4a0a0","datavalue":{"value":{"amount":"+0.81860447","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5894920$E5111FAE-A41D-454E-96E2-37398D03ABCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28beb981b9a34918e7e4a6871b2e7c8eee756213","datavalue":{"value":{"entity-type":"item","numeric-id":1773363,"id":"Q1773363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a883a18e52d693372f57db7863bc8a30a1c1d8c","datavalue":{"value":{"amount":"+0.8163011","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5894920$C0198F81-B884-4F7B-B1FD-13A4F42BDCFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bad5101ba16ada3d262435350cfcbbe5812df7d2","datavalue":{"value":{"entity-type":"item","numeric-id":4221701,"id":"Q4221701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4b616727f5e9e61e288bbb6325d5ed776c862a9","datavalue":{"value":{"amount":"+0.8110812","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5894920$B6EA4DBF-9ECD-47C1-99A3-125800C3A862","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Circular chromatic number and Mycielski graphs","badges":[]}}}}}