{"entities":{"Q5936037":{"pageid":8112839,"ns":120,"title":"Item:Q5936037","lastrevid":39827557,"modified":"2025-01-27T17:58:33Z","type":"item","id":"Q5936037","labels":{"en":{"language":"en","value":"Construction of sparse graphs with prescribed circular colorings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1612897"}},"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":"Q5936037$F6570308-1153-4224-A6D0-5394AA971436","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"91f2a583e18f34013000d51cfb5b316ab2430a43","datavalue":{"value":{"text":"Construction of sparse graphs with prescribed circular colorings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5936037$4D7387BE-8DC6-41FF-B2B6-A0E49107594A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"81590d7f43d1c091e8dcbdd34cb9b4a6bc76fbe6","datavalue":{"value":"0982.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936037$D4104915-9471-4423-A8B6-6E56AA157ED5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a20713418b54876aa2186c92bd000d901b65ef3","datavalue":{"value":"10.1016/S0012-365X(00)00246-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936037$F50E59B1-2F5F-4369-B617-10A5C969769D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380c4124a5ef272e2152da1b5d415130e3e64f8","datavalue":{"value":{"entity-type":"item","numeric-id":175596,"id":"Q175596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936037$19A06F1E-BD4B-4A84-9B06-F16285F535C4","rank":"normal"},{"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":"Q5936037$3141DAE9-4CE1-4B87-8390-3BAA59D954D4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936037$3D21CEAA-CFC4-4543-9E27-3ECDC641E449","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca81d64c0b12a62d219fb28ceff571fa6ba75361","datavalue":{"value":{"time":"+2002-02-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5936037$EC5B634A-1205-4A60-905F-8751E0E85A58","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cf3482fa1c38f5941df8464f18c140217a24dfbf","datavalue":{"value":"Suppose that \\(G=(V,E)\\) is a graph and \\(k,d\\) are positive integers with \\(k\\geq 2d\\) and \\((k,d)=1\\). A \\((k,d)\\)-coloring of \\(G\\) is a mapping \\(f:V\\rightarrow \\{0,1,\\ldots, k-1\\}\\) such that for every edge \\(xy\\in E\\), min\\(\\{|f(x)-f(y)|, k-|f(x)-f(y)|\\}\\geq d\\). In this paper the following property is constructively proved: If \\(k\\geq 3d-2, (k,d)=1\\), \\(A\\) is a finite set and \\(f_{1},\\ldots ,f_{n}\\) are mappings from \\(A\\) to \\(\\{0,1,\\ldots ,k-1\\}\\), then for any integer \\(l\\), there is a graph \\(G=(V,E)\\) of girth at least \\(l\\) with \\(A\\subset V\\), such that \\(G\\) has exactly \\(n\\) \\((k,d)\\)-colorings \\(g_1,\\dots, g_n\\) (up to a permutation of the colors), and each \\(g_{i}\\) is an extension of \\(f_{i}\\). This result generalizes a result of \\textit{V. M\u00fcller} who proved this for \\(k\\)-colorings [Discrete Math. 26, No. 2, 165-176 (1979; Zbl 0407.05037)]. Note that for \\(n=1\\), the method presented in this paper gives a construction of uniquely \\((k,d)\\)-colorable graphs. Some other results about the projectivity of the graphs \\(G_{d}^{k}\\) defined in the paper are also presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936037$1FEF5908-4BBE-49A9-A455-A2CB79C24D32","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936037$5A4039EF-32E3-4C90-A427-08E8DFB68F07","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936037$86CA05EC-8E05-4A5E-BDAD-0733E707742F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a2bacfc40ade1700fabbb32154b4eee44959028b","datavalue":{"value":"1612897","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936037$6D5AED48-0911-4DE8-AEDD-EE02033D4791","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a49459c2104b87d0601ed3d4aaa5cd8e1277ed0","datavalue":{"value":"circular chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936037$E9C4ADA1-C325-4121-904A-50B86A189A04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936037$E35BB6F2-F019-439D-A253-2BE96C8158E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936037$70CD6ACA-522E-4A4D-B67C-0924B113C122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bcb89a5fcdf890799016b02445ce676d48eaf3e","datavalue":{"value":"\\((k,d)\\)-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936037$ED12F5C8-E5C1-4601-8FF5-A041D8BD691A","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":"Q5936037$30EABBD4-BF7F-4B0A-B8A0-9D08F85807E2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"413e9dc6b6f333630890e3df24f39d4930da927a","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00246-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q5936037$47B13C59-8A31-4E72-A354-7E4D5AA71606","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5af4e836cb6b7f44e109289102781f97f2d94841","datavalue":{"value":"W2051131143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936037$ABB4F70E-CE34-429A-80B6-A5BA38EE7EBD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ac88dd94f442c7711434410e7a5fd200794acfc","datavalue":{"value":{"entity-type":"item","numeric-id":1777243,"id":"Q1777243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4feb03270fbb0ee1d1e60522488489b424da188","datavalue":{"value":{"amount":"+0.7168386","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":"Q5936037$9641C4B2-1EDD-48DA-866C-652D11FB36DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41d94eeddef26a924dbcf8e0d47e4a0f54d62cc5","datavalue":{"value":{"entity-type":"item","numeric-id":4892340,"id":"Q4892340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89b07d69d095bb031c24c528d8ffd0896eb448be","datavalue":{"value":{"amount":"+0.70938635","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":"Q5936037$AB84C39F-34C2-4D53-B996-0976183638A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1604fa62e7d0d87d69f959c45964eced314b2f9","datavalue":{"value":{"entity-type":"item","numeric-id":1377702,"id":"Q1377702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1df79c1100784c2761a7f54c6df5c371c7ace3a","datavalue":{"value":{"amount":"+0.70279205","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":"Q5936037$6CE940FF-3AA6-40A0-AC36-34229AFFB7E4","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":"644828153f5b93446640637afb8ed0d8e995b3d4","datavalue":{"value":{"amount":"+0.70277077","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":"Q5936037$B5E3E2F9-1296-4BA5-9A21-83AFDD9BCA7E","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":"beeffa217bc315dc4a106305194117403d65d3d1","datavalue":{"value":{"amount":"+0.7017409","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":"Q5936037$960FB4F0-9FD9-4CF5-8EAC-67BB2518D7C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a6445f3865922d127a83990a45af49cec0634ce","datavalue":{"value":{"entity-type":"item","numeric-id":284746,"id":"Q284746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06fd8c149397d0191bc5f817615a0d9d6512ce33","datavalue":{"value":{"amount":"+0.69915426","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":"Q5936037$3BC7CC36-BFF0-476C-8C96-FC5802894B30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b6d131f09f3789976a7720c728af5ce1c8c2b7e","datavalue":{"value":{"entity-type":"item","numeric-id":1584412,"id":"Q1584412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d13097625d29ef8d0cda1a1b7fa2b4e385dbc074","datavalue":{"value":{"amount":"+0.69766366","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":"Q5936037$71941D5B-887A-4131-96AB-97ED4080BF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a87e7480c372ce9dff1e13ff5ff72ef100d457ea","datavalue":{"value":{"entity-type":"item","numeric-id":3527239,"id":"Q3527239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7028ca080a14f0e298f742e7115c9d4ce74f791","datavalue":{"value":{"amount":"+0.6899012","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":"Q5936037$49A0EA77-EAE7-4BAC-8543-7F0CA4FE2E57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0c7edf151b6b513d5e9b9a0120cfa2c6000f949","datavalue":{"value":{"entity-type":"item","numeric-id":3487411,"id":"Q3487411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cf8f957ac076638cfa70fa1a69b034b5fd3469f","datavalue":{"value":{"amount":"+0.6881114","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":"Q5936037$5E528C69-34DF-49BA-BD3A-192E82841672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86432ad8469df839c784e577188936f2d875e85c","datavalue":{"value":{"entity-type":"item","numeric-id":3614482,"id":"Q3614482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b6756a4acdfa621057f14774deb0506846e62d4","datavalue":{"value":{"amount":"+0.6866549","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":"Q5936037$84AEC36F-7746-428D-BC08-673B4679D8EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5936037","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5936037"}}}}}