{"entities":{"Q1409583":{"pageid":1420323,"ns":120,"title":"Item:Q1409583","lastrevid":68639001,"modified":"2026-04-13T01:06:48Z","type":"item","id":"Q1409583","labels":{"en":{"language":"en","value":"An analogue of Haj\u00f3s' theorem for the circular chromatic number. II"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1993521"}},"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":"Q1409583$72B3221B-EDD4-4E27-9188-DF7493E06552","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2ce986954945d3a1c5e257749f8a73907e055866","datavalue":{"value":{"text":"An analogue of Haj\u00f3s' theorem for the circular chromatic number. II","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1409583$B9BA691B-DE05-481C-8691-65DFCF85C3E5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0a475286297260135e14b3cd4557961a47fa7ffa","datavalue":{"value":"1030.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1409583$DDC89081-9A48-4568-BDC7-284BDFA1D4D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6b19b09c7519f38384d021f845694abb1cfab04","datavalue":{"value":{"entity-type":"item","numeric-id":168189,"id":"Q168189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1409583$3819899F-F0CD-4184-9C7D-5679CC27ED82","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1409583$C6C7EEBD-9055-4635-BF55-0E8255798955","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ac7e457c13a6fc575ac6a3f0a43b59f9a10be41e","datavalue":{"value":{"time":"+2003-10-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1409583$AC06E185-777D-407A-9F2D-BDC8A27D8E35","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e94b577424bc0d84bb9ccf3dcb2f34211af696c","datavalue":{"value":"For a graph \\(G=\\left( V,E\\right) \\) an \\(r\\)-colouring \\(f\\) of \\(G\\) is a mapping \\(f:V\\rightarrow [0,r)\\) such that \\(1\\leq \\left|f\\left( x\\right) -f\\left( y\\right) \\right|\\leq r-1\\) for every edge \\(xy\\) of \\(G\\). The circular chromatic number \\(\\chi _{c}\\left( G\\right) \\) is the infimum of those \\(r\\) for which \\(G\\) has an \\(r\\)-colouring. For \\(k\\geq 2d\\) the circular complete graph \\(K_{k/d}\\) is the graph with vertex set \\(\\{0,1,\\ldots, k-1\\}\\) in which \\(i\\) is adjacent to \\(j\\) if and only if \\(d\\leq \\left|i-j\\right|\\leq k-d\\). In a previous paper [Proc. Am. Math. Soc. 129, 2845-2852 (2001; Zbl 0971.05042)] the author designed a set of graph operations and showed that, for \\(\\frac{k}{d}\\geq 3,\\) all graphs with \\(\\chi _{c}(G)\\geq \\frac{k}{d}\\) can be constructed from copies of the graph \\(K_{k/d}\\) by repeatedly applying these operations. In this paper he designs a set of graph operations to prove a similar result for the case \\(2\\leq \\frac{k}{d}<3.\\) The combination of these results is a complete analogue of Hajos' theorem (which states that every graph with chromatic number at least \\(k\\) can be constructed from copies of \\(K_{k}\\) by repeatedly applying three operations: adding vertices and edges, identifying nonadjacent vertices and applying Hajos' sum) for the circular chromatic number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1409583$9859C2D0-2BEA-4BB1-9640-0422A469AFE4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a442079b5f7b524052e3b9ba53793079a6d84fd","datavalue":{"value":{"entity-type":"item","numeric-id":266956,"id":"Q266956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1409583$BF44051E-9E25-448E-9E37-229742858355","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1409583$E769546A-7D63-47A7-8053-07D9828EEABB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"994e186adf9ba57a01aec00418b366add779ee0b","datavalue":{"value":"1993521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1409583$03827064-514A-4125-A1FB-B9432CC30EBD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a49459c2104b87d0601ed3d4aaa5cd8e1277ed0","datavalue":{"value":"circular chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1409583$1578E389-2B6F-4802-91F0-00D4F5676AE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52e32184a7758552d036e87737ec1795a1c19581","datavalue":{"value":"Hajos' Theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1409583$5AB1CFE1-BC46-4CF4-86CA-08128EB34005","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":"Q1409583$17816D6D-EBCD-4528-8BB5-9FD168A07D70","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"726b05a647a0e963ee360ed38957b10031b24ee1","datavalue":{"value":"https://doi.org/10.1007/s00373-002-0505-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1409583$A2F77912-CA34-45AE-8A90-176BD0B69120","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"796fed20daddcec3c514580c2b4e0ae3ad0e82e4","datavalue":{"value":"W2020733172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1409583$956E6539-86FF-4669-9E11-65F20D91D31C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4ec1722b8d92da644bbeed3643d55b2a7c30c34c","datavalue":{"value":"10.1007/S00373-002-0505-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1409583$7D79BE25-4913-4914-A315-F2B7F871C678","rank":"normal"}],"P1643":[{"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":"4125ec822967223f34e8ad7b03b0ef1a97b3e5d1","datavalue":{"value":{"amount":"+0.8190613","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":"Q1409583$810235E2-6634-41F1-9D33-57DF3D94AC9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbfd4f0b1fead4d5782dc9851f0199fda7c4028c","datavalue":{"value":{"entity-type":"item","numeric-id":2567409,"id":"Q2567409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4efa8da9180f31cb84003824c58c72cad1e590d","datavalue":{"value":{"amount":"+0.77930015","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":"Q1409583$3B3B01E2-BD63-48A8-9240-3857DF3FC07C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77985962b498a27f9c30c9b0bdc30c0cbc497645","datavalue":{"value":{"entity-type":"item","numeric-id":3424895,"id":"Q3424895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b574cd0a239f908001fffdea8cb67338ec8d27b","datavalue":{"value":{"amount":"+0.7765756","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":"Q1409583$6A03E8BD-BEFB-437E-ACED-C90826BAF018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab7166f016108d4d62ed1485eaf7a899f216ec14","datavalue":{"value":{"entity-type":"item","numeric-id":1880798,"id":"Q1880798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3ba648f80285e059fcceaf3b6153903a17285fe","datavalue":{"value":{"amount":"+0.7762656","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":"Q1409583$0BDC0C4F-C075-4428-AA91-FBB7AB3FA922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71de653d967fe3df2cb5928041b31d88db97451c","datavalue":{"value":{"entity-type":"item","numeric-id":5491998,"id":"Q5491998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdd0a1ead36ae57014010138d2a8cac31c722262","datavalue":{"value":{"amount":"+0.7741867","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":"Q1409583$CCE52DBA-4C35-40A7-95CC-1257FD382D9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"707c80dc69e27ce24e48c56a27ff32f61845f944","datavalue":{"value":{"entity-type":"item","numeric-id":5429791,"id":"Q5429791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99cfe8f5e1978bc2d3b071775515391be3f79037","datavalue":{"value":{"amount":"+0.76217306","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":"Q1409583$7CBAA037-581F-48A1-ABA1-AB0BEC1548FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"485d2a0be26c3c1c1afbf2f2575abbf18536631b","datavalue":{"value":{"entity-type":"item","numeric-id":1125613,"id":"Q1125613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f834a9ca892226ae8be3f1fb2861d209bde64d91","datavalue":{"value":{"amount":"+0.7586963","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":"Q1409583$7A7F3813-B717-4255-845E-7FFA278E31C8","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":"55a63e9c2be4f9d3aac6718e6b2ede5966188e1e","datavalue":{"value":{"amount":"+0.7558973","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":"Q1409583$72BD8966-3A3F-42FE-805C-2F8F6571850D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6288a913dd53024c3c872e44d0a2a68dd2bdcff9","datavalue":{"value":{"entity-type":"item","numeric-id":4545983,"id":"Q4545983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6adc304f8b56684e6c44fb31e13676a9ca906d5a","datavalue":{"value":{"amount":"+0.7557804","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":"Q1409583$01780E40-6641-4773-AC22-0585CD1F6916","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1bebb0508c036e58ae1cf2156f0fbb0f84ea4c5","datavalue":{"value":{"entity-type":"item","numeric-id":4455327,"id":"Q4455327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3120cb2192183063a85420961679c0ce74b1ab39","datavalue":{"value":{"amount":"+0.7535354","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":"Q1409583$0B70EE69-EB07-403B-B8FF-E9ED7B6CC006","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An analogue of Haj\u00f3s' theorem for the circular chromatic number. II","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_analogue_of_Haj%C3%B3s%27_theorem_for_the_circular_chromatic_number._II"}}}}}