{"entities":{"Q2380224":{"pageid":2390967,"ns":120,"title":"Item:Q2380224","lastrevid":72652254,"modified":"2026-04-14T06:19:00Z","type":"item","id":"Q2380224","labels":{"en":{"language":"en","value":"Bipartite coverings and the chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5686773"}},"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":"Q2380224$2091AFA0-483D-4CBB-A67F-54222461DB7E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e04525d3ee03f3a7fc11ec1bc8f60703dd6719b1","datavalue":{"value":{"text":"Bipartite coverings and the chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2380224$E7502439-7C7D-406C-929B-EE52387A64C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8e5720961881755c416374b19137692b4999ee2e","datavalue":{"value":"1186.05099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380224$7C255664-C85A-4363-B34E-A408EE8B3FE4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b2dc7fb86714f67c87c73e07c13ee1e0d7b9d71","datavalue":{"value":{"entity-type":"item","numeric-id":168649,"id":"Q168649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380224$5E080C6C-90A3-4392-BC92-9B3FC6D5893C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"256f08c4eec31eb6356087b348ec0eaa953e3474","datavalue":{"value":{"entity-type":"item","numeric-id":879398,"id":"Q879398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2380224$5F0981D5-F3BA-4695-AC38-D01508D05E87","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":"Q2380224$C8E78EE6-2201-4352-9A1E-A6045832940D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"143e8774a45e663375c24b3b343519cf2933b18c","datavalue":{"value":{"time":"+2010-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2380224$0095DAB1-210C-47B0-BEB0-C1B2FAD988C0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6f88ebd45c75bb093a8c03ef38bfe95836059421","datavalue":{"value":"https://arxiv.org/abs/0903.3048","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380224$0E808342-55B6-4190-947B-851FCE650F41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"1544c31858df10e41e6b11decb1e417a42d4c723","datavalue":{"value":"https://eudml.org/doc/228137","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380224$AD6F7A8E-F62B-4118-9F16-2BF80B300548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ddfcd8166e579989ea04098b84efd6465444f163","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1n34.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380224$73ECEE9C-D8DB-48A5-8B77-233AB33C3F38","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4a8d095febeb5375c0224fdd64becf25bc9f4336","datavalue":{"value":"Summary: Consider a graph \\(G\\) with chromatic number \\(k\\) and a collection of complete bipartite graphs, or bicliques, that cover the edges of \\(G\\). We prove the following two results: {\\parindent=4mm \\begin{itemize}\\item[{\\(\\bullet\\)}] If the bipartite graphs form a partition of the edges of \\(G\\), then their number is at least \\(2^{\\sqrt{\\log_2k}}\\). This is the first improvement of the easy lower bound of \\(\\log_2k\\), while the Alon-Saks-Seymour conjecture states that this can be improved to \\(k-1\\). \\item[{\\(\\bullet\\)}] The sum of the orders of the bipartite graphs in the cover is at least \\((1-o(1))k\\log_2k\\). This generalizes, in asymptotic form, a result of \\textit{G. Katona} and \\textit{E. Szemer\u00e9di} [Stud. Sci. Math. Hung. 2, 23--28 (1967; Zbl 0147.42804)] who proved that the minimum is \\(k\\log_2k\\) when \\(G\\) is a clique.   \\end{itemize}}","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380224$D93E2AFF-B05F-460E-A76B-A8B887BD43CD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380224$8519BC3F-47B4-42C2-B154-DEBC65BE689F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380224$03EF8177-953A-46B8-98EA-58A0C436CC03","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2de5924acf64b1978dcf4968062a9a49f1d8c652","datavalue":{"value":"5686773","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380224$71D833C1-EC6C-4B8F-AB19-B33223111B7C","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":"Q2380224$553CF63E-4C2A-4F11-A419-F7710E648B73","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"af0a73b9a03b5420da0dc3ac9a24f61bdb2a36f3","datavalue":{"value":"bafkreifgsv4kjm2lqjiszdynalxnzexzkxrvj6vuc6ofijljszphyvjneu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380224$7632D83D-6352-4841-B986-D56C70FBD0EA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed11b97addd98b3e8041e3d48431c40486a16730","datavalue":{"value":{"entity-type":"item","numeric-id":4354593,"id":"Q4354593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2515d034252ad5a2b94d541ddbfe355d21196bb7","datavalue":{"value":{"amount":"+0.8188639879226685","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":"Q2380224$7E1710A7-A3D0-4238-B671-E1488F7E20FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4494f75235fa07f861cb83847d307760e389f8ff","datavalue":{"value":{"entity-type":"item","numeric-id":4594195,"id":"Q4594195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f06d42e2cedb3ae008e7781e54c379ac45a7524","datavalue":{"value":{"amount":"+0.8145941495895386","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":"Q2380224$F6EAE93D-B655-4E99-8559-502DF692F2A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d74832bd780d87b96e963b0d41431e4c5088a5db","datavalue":{"value":{"entity-type":"item","numeric-id":2121747,"id":"Q2121747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f929d2635da2a202e7484c2841d9549a0a44e91","datavalue":{"value":{"amount":"+0.8081220984458923","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":"Q2380224$68D23649-F350-4F9C-9544-B9AF6ADC2843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"593be0bfddf434891013c2b4c989591c302541d1","datavalue":{"value":{"entity-type":"item","numeric-id":5461529,"id":"Q5461529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ecada39aa6442028e746ff4a84657b2665cc4e5","datavalue":{"value":{"amount":"+0.799649178981781","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":"Q2380224$E3B627BE-F064-4269-8991-2C7B14D847A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2578eea6cd7035e857800f31de69233fc09b4712","datavalue":{"value":{"entity-type":"item","numeric-id":3312268,"id":"Q3312268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1e4915d52c69f7bcdc240c23e537c0bf56bb7fd","datavalue":{"value":{"amount":"+0.7981609106063843","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":"Q2380224$3614074E-0C66-4E3D-A688-3D3E00FF6E12","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bipartite coverings and the chromatic number","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bipartite_coverings_and_the_chromatic_number"}}}}}