{"entities":{"Q2175801":{"pageid":2186544,"ns":120,"title":"Item:Q2175801","lastrevid":53720948,"modified":"2026-01-25T14:55:25Z","type":"item","id":"Q2175801","labels":{"en":{"language":"en","value":"The minimum number of edges in 4-critical digraphs of given order"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7195258"}},"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":"Q2175801$BDBF9344-FF86-4BB6-94FF-9547890EFB4D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a537ee5b7e29ee907816878ec2a389f934e137c8","datavalue":{"value":{"text":"The minimum number of edges in 4-critical digraphs of given order","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2175801$3ED57769-7CA8-47A8-BFBE-B89DA326E3F8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"076b3494e6091989f4dbc5dbac0b6555fdf93742","datavalue":{"value":"1441.05080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175801$E969FE86-C61E-4518-A6A2-66525A752F37","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6f7473d760a44eaadfe0ee28c772e95cb7f6f55","datavalue":{"value":{"entity-type":"item","numeric-id":286764,"id":"Q286764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$07F808D9-9DA9-410F-B80B-5B7EF7E82C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a112fcddf40de3e0f26627c12549da4365ccc05","datavalue":{"value":{"entity-type":"item","numeric-id":214987,"id":"Q214987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$7F18454E-4BF2-4A70-A384-29255E237E6B","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":"Q2175801$7B60179B-FB97-4EAA-83A0-393BFFDB5C20","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dde1b11a90e0e18f0bcca3b838f9ec9fe003c840","datavalue":{"value":{"time":"+2020-04-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2175801$B58B738E-88D2-46A4-BDC5-7A723674E296","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"296891b3b575f4b9c53d972cfb98264963fba0b0","datavalue":{"value":"The authors consider the problem of finding critical graphs for coloring of directed graphs, the model defined by \\textit{V. Neumann-Lara} [J. Comb. Theory, Ser. B 33, 265--270 (1982; Zbl 0506.05031)]. The dichromatic number \\(\\chi(D)\\) of a directed graph \\(D\\) is the smallest number \\(k\\) for which \\(D\\) has a coloring such that each vertex receives a color and no directed cycle of \\(D\\) is monochromatic (acyclic coloring). Let \\(d_k(n)\\) denote the number of the minimum number of arc possible in a \\(k\\)-critical digraph of order \\(n\\). The paper gives proof that \\(d_4(n) \\geq \\lceil (10n-4)/3\\rceil\\) for all \\(n\\geq 4\\) and \\(n\\not = 5\\).  The results presented in the paper complete the knowledge in the subject under consideration. Up to know the problem of \\(k\\)-critical graphs for coloring of directed graphs were known for \\(k\\leq 3\\). Thus, the contribution is significant.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2175801$02E031BD-39B1-4764-B15B-17720C0208C4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"aee79d242f75af733e0d4fce649011872d9aabae","datavalue":{"value":{"entity-type":"item","numeric-id":298965,"id":"Q298965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$C983B560-9645-4DC1-BA5A-77ACC46ADB8E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175801$0AB90F9F-D6E6-4F02-B8DB-460CDF4FB56F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175801$AD51AF4E-3F90-4565-B28C-3F263F018E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175801$E6B16249-D7EC-4E17-83A3-1052BF824B11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175801$2C46BED4-C215-4FD6-8923-396C686CABBC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ae3d67a98dd52ad9a6b2e6b4e25d4541f27793e3","datavalue":{"value":"7195258","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175801$0882D230-3B22-40E7-AF6E-F96537FA7A3C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a73f6c2b7b78ccca68f4ac7fd59c2fa3c064ce0","datavalue":{"value":"coloring graphs and digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2175801$D9B569CB-C987-48ED-82C3-3637B98C158E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be4a87f4a7c17e610f0e5c1957a769703788d58c","datavalue":{"value":"critical graphs and digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2175801$31855E88-BDF7-4AEC-B2C0-5242770DCEF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b10cff0c23b9f6aa8789d5f16a4c9af5f5c9cb04","datavalue":{"value":"average degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2175801$5C42F21C-637C-4D14-9B99-FC606B905A36","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":"Q2175801$7EBB5D5A-79CE-4AAE-8196-9103F7F24CEF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0517de4c13537a0a7f58eb587a5d57209ed2b5e9","datavalue":{"value":"https://doi.org/10.1007/s00373-020-02147-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q2175801$E9126E33-B813-4F02-9F92-D54DC39AB99E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"131b448e928080e74c48e419181f30d4f54dc4c4","datavalue":{"value":"W3006087353","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175801$DBA40198-68F1-4F8A-B2B4-17263B34A05F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a36116571a199d88dbac894a12c3c3ecc00005d9","datavalue":{"value":{"entity-type":"item","numeric-id":2309234,"id":"Q2309234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$124C40D8-591C-4301-909B-C8809BD49BEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d55ca695ac6adc014253990f6ebae2da8b2f4288","datavalue":{"value":{"entity-type":"item","numeric-id":4474287,"id":"Q4474287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$0ED21A53-5BB3-4092-B8EF-554F504CD8EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85cfa63f67ed3743ed6d983c37c02f4185c5f671","datavalue":{"value":{"entity-type":"item","numeric-id":5811782,"id":"Q5811782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$7164DBFA-34FB-4F28-BB76-E34A89DD1C92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24740898104d4c73d726dfe5ed5c3a2648f291b3","datavalue":{"value":{"entity-type":"item","numeric-id":5821654,"id":"Q5821654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$73AACDFD-BF98-4231-818A-0E1172C08BB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b5a77f691c73d3cc84a775a0deb455c68b0dbbc","datavalue":{"value":{"entity-type":"item","numeric-id":3241662,"id":"Q3241662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$F867E1C1-5F61-4305-A336-3F1E0E1C5E5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02c160b73834e9fd25d1d5c33f3764e4deb50849","datavalue":{"value":{"entity-type":"item","numeric-id":4052158,"id":"Q4052158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$E29F5480-3F86-4E6C-B1E4-F297E7CFC003","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":"Q2175801$BA5A92A5-FFB7-449B-938C-CA9524EF12E4","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":"Q2175801$229CE610-FCE9-440B-BBAE-6B6AED1FABAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f08c5112edf7f837490d497bb2f3820e4c72b45","datavalue":{"value":{"entity-type":"item","numeric-id":5732334,"id":"Q5732334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$2E6126CA-DB7C-42C6-821F-F1AA223A834C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4d4fb0d146535ef37cc221544e998161ff87740","datavalue":{"value":{"entity-type":"item","numeric-id":5520564,"id":"Q5520564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$30CAF5CA-2595-429B-8A44-2E9C8C262921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47491630b132e7c5e40a72bab918760c071c2a41","datavalue":{"value":{"entity-type":"item","numeric-id":267198,"id":"Q267198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$C3F3F4EC-2EA5-4E94-8244-0C7CBE08DAC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c92938728dfb35bbc782701af20f73c60ce0170","datavalue":{"value":{"entity-type":"item","numeric-id":640457,"id":"Q640457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$D1939B45-63EE-4E42-A803-A1844F97FFB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a634964612a8cdaf1823f922d79f7f7e8606f3a","datavalue":{"value":{"entity-type":"item","numeric-id":5477816,"id":"Q5477816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$1E062835-348A-4372-BFA9-E1D4DB8175A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15b90894cc19cc291f3276344b9c21ec64f6c5df","datavalue":{"value":{"entity-type":"item","numeric-id":462926,"id":"Q462926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$E619C978-8AB9-4F00-92B7-C3F300F8805D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68bfa7d7f59d59d96a9c14c4f44c7b1d0fe4cd40","datavalue":{"value":{"entity-type":"item","numeric-id":397076,"id":"Q397076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$2B355014-2419-4DB7-8285-4C0F84F2B786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b26688ad0a58910eda60809a6e3cf7d71438c0ea","datavalue":{"value":{"entity-type":"item","numeric-id":5361236,"id":"Q5361236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$AF2206EB-CCB1-4166-A519-AC70966C4FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b96974a3f4dddd75ae679cddfd131453f8bf5970","datavalue":{"value":{"entity-type":"item","numeric-id":962116,"id":"Q962116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$B76F334B-4C6A-41D5-B7E2-A99579172BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9799935fa6b5975808f92cfcc703600c2e6e3c88","datavalue":{"value":{"entity-type":"item","numeric-id":2726740,"id":"Q2726740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$DF0AFA4E-2605-43B5-8167-5F1D045A8B2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f7582221e8b128b2b7618c56d5a235add68c2e1","datavalue":{"value":{"entity-type":"item","numeric-id":1343264,"id":"Q1343264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$ADE8BAC7-4955-4E1F-8A83-CE40327DB4BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ec3dc3a44ac90b481428356217258d9af116d72","datavalue":{"value":{"entity-type":"item","numeric-id":2822589,"id":"Q2822589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175801$69FA6832-E380-4B8B-A46F-46B312A69AF0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cb699b56845762f83df6bb5da9afdd9821418337","datavalue":{"value":"10.1007/S00373-020-02147-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175801$165A0279-7D86-4BB1-8E0C-90FA8C40E77B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce8f4a161948f53aecc13ae9237597024cc35d9e","datavalue":{"value":{"entity-type":"item","numeric-id":2309234,"id":"Q2309234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f66050359d4863e7725a6ddf5bfeab4fd81d8521","datavalue":{"value":{"amount":"+0.8242821097373962","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":"Q2175801$E781B6EB-9872-4CFF-AE75-DEB2F8CF36A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"deb9925f4502860c25570418af9bdac727ce61b4","datavalue":{"value":{"entity-type":"item","numeric-id":1343264,"id":"Q1343264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"040f4491fd8f7abe5724fbc8c995b1b0dca0d787","datavalue":{"value":{"amount":"+0.8092885613441467","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":"Q2175801$D84F005E-D0EF-4D77-8577-88B82027F861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03dced01792073281f3f6d1294f8ebcb9a04d0cd","datavalue":{"value":{"entity-type":"item","numeric-id":788737,"id":"Q788737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e66cf70f080e40f4dee3a073cb5ff18c7ba4bf87","datavalue":{"value":{"amount":"+0.8092208504676819","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":"Q2175801$54B68D8E-F0EC-4EFF-9F56-C784DE44977D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91b44273868fc309212a2746ffacd1f2060f046e","datavalue":{"value":{"entity-type":"item","numeric-id":3693540,"id":"Q3693540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eba42c957f2b6ba6bad6151adcbe02332e1b7ba6","datavalue":{"value":{"amount":"+0.8015952706336975","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":"Q2175801$B53EB114-A83E-4FF1-A8D9-847A69DE7BDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16c5c17de3d7c83b17cbb0291cf94d1f0ee556cf","datavalue":{"value":{"entity-type":"item","numeric-id":2725183,"id":"Q2725183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42be4a59a1f8069db3b205df5d3428d60ac0a12d","datavalue":{"value":{"amount":"+0.7880398631095886","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":"Q2175801$6754A446-FEF4-4409-983D-465F308543CC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2175801","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2175801"}}}}}