{"entities":{"Q2094868":{"pageid":2105611,"ns":120,"title":"Item:Q2094868","lastrevid":57724881,"modified":"2026-04-01T02:54:23Z","type":"item","id":"Q2094868","labels":{"en":{"language":"en","value":"Digraphs with all induced directed cycles of the same length are not \\(\\vec{\\chi}\\)-bounded"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7613659"}},"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":"Q2094868$59603EAE-7FD0-4ADA-805A-C6069AA02CF4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"364e5041b9d23a6875580831b72512264cf1d2c9","datavalue":{"value":{"text":"Digraphs with all induced directed cycles of the same length are not \\(\\vec{\\chi}\\)-bounded","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2094868$97499B6C-0CE9-4974-9843-BE2FB1001B6E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"99ccff08d0a4a532923ad97b5adf7c3c45d76cbf","datavalue":{"value":"1503.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094868$543209B9-B6BA-4262-9D94-B03A83D004A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bb7e729bc684c55a3a7fbea77e03a97512a9bc37","datavalue":{"value":"10.37236/11179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094868$1BC3E217-4532-4BF8-AFA5-C1AB3B99F9F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c6e35f9a253cefd23a5e4d8a38d579c08a081b9","datavalue":{"value":{"entity-type":"item","numeric-id":2094867,"id":"Q2094867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$CA71AFCE-58F6-46AF-81F7-091240CB264A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e276f41dd1fb59e1558a62fd6ae6e26b774b975","datavalue":{"value":{"entity-type":"item","numeric-id":2005716,"id":"Q2005716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$8D6E2599-EB5F-4AE5-9BC1-A2997903C403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c8a2fe2934bcec8ef3f374226e3e5af35d3c6da","datavalue":{"value":{"entity-type":"item","numeric-id":301586,"id":"Q301586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$EFE1944E-EFB9-4232-89EF-307BE601AC49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f84c2585906a3dfec8dc78c048cfc8b3b8be2285","datavalue":{"value":{"entity-type":"item","numeric-id":345122,"id":"Q345122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$2316A708-BF81-400F-A381-3F6CDDB88C76","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":"Q2094868$B7FDD595-12E0-4A89-A06E-9FB73481FBB2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41c2d4b2b9eee3d1d4724659108ff6928154d594","datavalue":{"value":{"time":"+2022-11-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2094868$F06EBF2E-16C5-4A31-BC6B-04D615C17E78","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"46764c79d17c736730ec53a3e6f348ce2e2b63ea","datavalue":{"value":"https://arxiv.org/abs/2203.15575","type":"string"},"datatype":"url"},"type":"statement","id":"Q2094868$2312804B-3CC1-4248-A822-129E99A078D2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c0b708d8b152c4e4b51e36a42008e86e70b74ab0","datavalue":{"value":"Stimulated by challenges for the dichromatic number, the authors establish that the family of graphs where each triangle-free induced subgraph has bounded chromatic number is not \\(\\chi\\)-bounded. They also raise a number of open problems for the researchers who are interested in this topic. In fact, they ask in particular, whether the family of digraphs with every induced directed cycle of length \\(t\\), is \\(\\vec{\\chi}\\)-bounded for a fixed integer \\(t>3\\). \\textit{P. Aboulker} et al. [ibid. 29, No. 2, Research Paper P2.17, 5 p. (2022; Zbl 1493.05130)] answered the authors' question in the negative for \\(t = 3\\). The authors in this article extend this negative answer to all \\(t\\) greater than or equal to 3. Even though \\(t\\)-chordal graphs are not \\(\\vec{\\chi}\\)-bounded the authors establish that deciding whether a digraph is \\(t\\)-chordal is coNP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094868$04F7C6FE-CC18-43BE-ABE4-E06C5309318D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c754ec9fae75fbeaa94e089f2452dc68e1235b5c","datavalue":{"value":{"entity-type":"item","numeric-id":198726,"id":"Q198726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$CF846EA6-1E20-42FD-AE74-6CAC8CD0B8F5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094868$12B81178-11E1-4095-9D1E-73DAF6DB641E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094868$66CEFD87-6990-4328-84C6-6A09048313FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094868$2BC2EB57-D355-4C70-BE2B-34674C00D5CA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"636ba872719f12456bf49cebae207b3d6d0c8bed","datavalue":{"value":"7613659","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094868$BC529AE2-947E-4CF8-9BCE-A864C6843C80","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffa219ea2cff89df5162edb57bd2a31ea73e1a26","datavalue":{"value":"digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094868$21D62BEF-D958-4732-A187-70B5D57A74BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4731718af57455148a124b7612e67a771e79ae8a","datavalue":{"value":"\\(t\\)-chordal","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094868$752EEBE3-5F8B-471F-945B-5AD8F8A11292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"edc80d276908747cd1ade9a76616810aca402ed5","datavalue":{"value":"dichromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094868$EEF47E45-4407-4F18-91B3-F22279CCAAD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb2169375ebb26ec0067c3fe2ae2119dcb9b464e","datavalue":{"value":"clique number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094868$752A3CA7-0C06-4206-BA36-AB5B6EE19955","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":"Q2094868$3C7F4419-8D2E-4B44-B0AB-A7C575FC1CD5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6621de476bd2d25ea9d3d95ea12d9021b4391e64","datavalue":{"value":"W4306652466","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094868$EF51EBB0-D952-45E9-BA42-3FCE14226C05","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f77de644707661fb9f941fb5dc5f444e48aa31c","datavalue":{"value":{"entity-type":"item","numeric-id":2138574,"id":"Q2138574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$EBEFB79E-2341-4B1B-B8D9-955FD15D8CFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82cfa9f684c3350648874deb95288407da9381e","datavalue":{"value":{"entity-type":"item","numeric-id":1175980,"id":"Q1175980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$B799B6FA-BB25-428D-8513-3B331C461559","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23424bc68296e7051f58c9c9e65bd7e357a03180","datavalue":{"value":{"entity-type":"item","numeric-id":2101164,"id":"Q2101164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$197A3B3D-26B3-4E50-9569-8529853819C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"440136c265b65367e887b4d312111aeb048b14c4","datavalue":{"value":{"entity-type":"item","numeric-id":3882513,"id":"Q3882513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$445C86FE-F4B8-4F53-84D8-B81938611731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b8b57677a0d06c6630de1f95258ead75ed89053","datavalue":{"value":{"entity-type":"item","numeric-id":4063176,"id":"Q4063176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$FBA91356-F104-4F10-AD48-A748DDDB1923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02980cf4411eb7f6e0f0dbda88fb746e9b54abf0","datavalue":{"value":{"entity-type":"item","numeric-id":3503839,"id":"Q3503839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$6C284824-A040-450F-9B9B-BB8210B10CB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2d371018a3fa7b0a8768b2d9ef7ec9c500ed97c","datavalue":{"value":{"entity-type":"item","numeric-id":1120591,"id":"Q1120591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$5B6258DA-8D33-4481-8730-A7942F9D0345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c3ed573aab1340e3f01f3d7d04ea69b64bec434","datavalue":{"value":{"entity-type":"item","numeric-id":1836671,"id":"Q1836671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$2875A361-143F-49B6-8EBD-A910A4B634FA","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"4c209334d351cf081e7b02504b0e8b0c8870b20d","datavalue":{"value":"bafkreigv3r65arogts5cvz5rm6jjcd5fg7ef2x3f6rzlnswvxcq7rb6x7e","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094868$6BDA98A5-D99B-42ED-8CAD-17FFD207669D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0477eba23350e06f77f4afba1282e1fc0c8442b6","datavalue":{"value":{"entity-type":"item","numeric-id":2138574,"id":"Q2138574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0f15bd267047c8fbbe323de1178e6d5de329efb","datavalue":{"value":{"amount":"+0.8770838975906372","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":"Q2094868$E06D33F3-5212-487D-BD81-3D35E063B72C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca2647a6f2b2cf517c1173be0402d9b1d1a6fb7a","datavalue":{"value":{"entity-type":"item","numeric-id":2004076,"id":"Q2004076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63ed6ab1e47d2f5c6209fa5f39fb81ebb7abde2c","datavalue":{"value":{"amount":"+0.8543435335159302","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":"Q2094868$06959963-41A4-4DC2-8149-9853D6AB7CBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1568cccca10992065f5dec1646b6145cc38ed0f7","datavalue":{"value":{"entity-type":"item","numeric-id":2030749,"id":"Q2030749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d8318b8f55297b87e7c31efd0232d4b09e0b1ac","datavalue":{"value":{"amount":"+0.7772852182388306","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":"Q2094868$3C92CE54-ED0C-4C8D-91AA-65E09248A7CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c6d40bbccdc77311ec5be7bd4ab94c7d2aee80d","datavalue":{"value":{"entity-type":"item","numeric-id":1633601,"id":"Q1633601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4da5a3f4f384fe15efe970f503d5820f8f864bad","datavalue":{"value":{"amount":"+0.7760535478591919","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":"Q2094868$5FBAB14E-1304-4857-BC50-D70569418F80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"604a6e6691638b5197b87a011ec0ede18d579480","datavalue":{"value":{"entity-type":"item","numeric-id":4646938,"id":"Q4646938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d9929e914c8b42d18760f8b1350d27d3e9da309","datavalue":{"value":{"amount":"+0.7723187804222107","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":"Q2094868$A025B9B7-2FB9-4C42-A233-7804734DA290","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094868$6306B545-D439-47C2-B696-6198834EB260","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2094868","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2094868"}}}}}