{"entities":{"Q640457":{"pageid":642305,"ns":120,"title":"Item:Q640457","lastrevid":57084396,"modified":"2026-03-26T13:08:16Z","type":"item","id":"Q640457","labels":{"en":{"language":"en","value":"Strengthened Brooks' theorem for digraphs of girth at least three"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5960057"}},"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":"Q640457$82AAE953-CD29-498C-95BF-89FC91F73221","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"992586470aa8cce3d484a540664bb166a0b1745d","datavalue":{"value":{"text":"Strengthened Brooks' theorem for digraphs of girth at least three","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q640457$29E93AB6-30AE-4CDB-B85A-BDE48B47CCDE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"48ce6e4d40839a38129cbbcaeeab7a13167edaf9","datavalue":{"value":"1230.05129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640457$DE57E206-9EFB-4FFE-B4B9-E90066F02361","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cc1acfa2a56833d0abfefa41fbed86cd0ca258d","datavalue":{"value":{"entity-type":"item","numeric-id":418895,"id":"Q418895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640457$76B9A9CE-4752-4D1B-A688-D4A9C5A1D8E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96650f014ad2d7966e931e79230c3a74fac9c2f8","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640457$692ED964-8399-4DAB-BA54-FD0E9DDB0F82","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":"Q640457$0EC2BE6F-9919-4031-A9D9-043287A28E40","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9767fe8dd1d6f9791ae763e9a67550b5f9aa27e1","datavalue":{"value":{"time":"+2011-10-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q640457$9DAECC2B-794F-4064-B2F3-ECD94A66662A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"24be8a6394088f027f56fb83d500379bd7df27a7","datavalue":{"value":"https://arxiv.org/abs/1110.4896","type":"string"},"datatype":"url"},"type":"statement","id":"Q640457$C67F868B-96A8-4709-89D0-494E572BCDA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"78bc9e0b5d83152cd01416accc27bc2793565d13","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p195.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q640457$73E65488-FF5E-4572-AF53-FD4F256ED5E3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"39c4f76e497b4f6f0d9a88ea9c8f0047aa65ee24","datavalue":{"value":"Summary: Brooks' Theorem states that a connected graph \\(G\\) of maximum degree \\(\\Delta\\) has chromatic number at most \\(\\Delta\\), unless \\(G\\) is an odd cycle or a complete graph. A result of \\textit{A. Johansson} [Asymptotic choice number for triangle free graphs, DIMACS Technical Report, 91--95 (1996)] shows that if \\(G\\) is triangle-free, then the chromatic number drops to \\(O(\\Delta/\\log\\Delta)\\).   In this paper, we derive a weak analog for the chromatic number of digraphs. We show that every (loopless) digraph \\(D\\) without directed cycles of length two has chromatic number \\(\\chi(D)\\leq(1- e^{-13})\\widetilde\\Delta\\), where \\(\\widetilde\\Delta\\) is the maximum geometric mean of the out-degree and in-degree of a vertex in \\(D\\), when \\(\\widetilde\\Delta\\) is sufficiently large. As a corollary it is proved that there exists an absolute constant \\(\\alpha< 1\\) such that \\(\\chi(D)\\leq\\alpha(\\widetilde\\Delta+ 1)\\) for every \\(\\widetilde\\Delta> 2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q640457$7E3B6691-BA1A-4937-A1A8-423BC64060FC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640457$9370EB51-7E4D-4C6E-8EF6-20240E8FF7C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640457$CF21055C-47E0-4581-8636-E3146FCB923E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a36488cfa5dad0aad8732c1bc5691ba72626d15b","datavalue":{"value":"5960057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640457$F7E155C0-5C69-4EE0-8624-598AA442787E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92491b612f9666e05ce4e8c57837d911db50179b","datavalue":{"value":"digraph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q640457$1538090A-88BB-4B77-9BC6-0E83FAEBCD0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"edc80d276908747cd1ade9a76616810aca402ed5","datavalue":{"value":"dichromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q640457$8C60B336-30CE-4F88-A1A2-AA94CCA95763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d4b22234c75d530f64241b56947fa988d206e61","datavalue":{"value":"Brooks theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q640457$E324BF8F-892B-4333-9215-2F63D0767963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7e0835466d651ee6f68a44f357d17b68b56dee7","datavalue":{"value":"digon","type":"string"},"datatype":"string"},"type":"statement","id":"Q640457$37CFB8CC-93B0-43EF-973C-21885B10BC32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16dc7a89044d7b0f792db4d50d4a7de618c9db54","datavalue":{"value":"sparse digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q640457$21ED3C6C-081B-4B1D-BC5B-2847364A2E42","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":"Q640457$41EDE766-6134-44E3-9FD4-11CA6929BFC7","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"2fc6c68f6446e33aef1df8e936531a2f46288cbc","datavalue":{"value":"bafkreifjbxrwedxn3ptttz7k5xaywcksc7c5zu2fhtk5gf44gz6g6hza5i","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640457$E67D4688-9379-468B-B37C-6757888F9626","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acd76c19a7c8f7cb043808a4e58466abd06ee334","datavalue":{"value":{"entity-type":"item","numeric-id":418896,"id":"Q418896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ed423712266a8b71ce2609e4195f5f37a5a7f20","datavalue":{"value":{"amount":"+0.8499263525009155","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":"Q640457$CE5EFD54-553F-48A6-BF6E-2FB68A4DBD95","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":"c608bc9ae965e4db0a426f253306a1caef6b883f","datavalue":{"value":{"amount":"+0.8413084745407104","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":"Q640457$E5D73861-95B6-4DDC-89F6-BB6F38A0C61A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8d932f54e52ebe5a8ff8d820d6eb1f04da45196","datavalue":{"value":{"entity-type":"item","numeric-id":2848530,"id":"Q2848530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9181c043366dc9177547bd75b04a17ffcf763c6e","datavalue":{"value":{"amount":"+0.8326413631439209","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":"Q640457$C7DBDDF0-34A2-4BA1-9924-141737B9E96F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7db35f9d609fda629a7844f3c39274044d3c283","datavalue":{"value":{"entity-type":"item","numeric-id":4852428,"id":"Q4852428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1ff0fd118d1895ff90195590e4c6cd279f699e4","datavalue":{"value":{"amount":"+0.8271504640579224","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":"Q640457$2B1C5CBD-90A2-48C3-89C6-C23205B00FD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4f478fc0f5f1ebc1c68be2c5b3c6d848f3a010c","datavalue":{"value":{"entity-type":"item","numeric-id":267198,"id":"Q267198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aceea930f225c7b8f7555e49e3f4e68b245e8c38","datavalue":{"value":{"amount":"+0.8078702092170715","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":"Q640457$C3A780DE-C5F7-4E65-B9F2-B177011D24DB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:640457","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:640457"}}}}}