{"entities":{"Q1186126":{"pageid":1196875,"ns":120,"title":"Item:Q1186126","lastrevid":69844668,"modified":"2026-04-13T10:43:47Z","type":"item","id":"Q1186126","labels":{"en":{"language":"en","value":"Multicolored forests in bipartite decompositions of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 36236"}},"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":"Q1186126$12A7625A-CF11-4D2B-9C14-9F15759C05A5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3edf760dcdc69c9d1d476e3dae5e61fa7f4be0a4","datavalue":{"value":{"text":"Multicolored forests in bipartite decompositions of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186126$FE6D174E-E3CC-4ED4-B036-47969E678978","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b289df3c3ab546d29648bd73a5759e44570cdc35","datavalue":{"value":"0763.05075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186126$5E75FEFC-BBF5-4D95-958D-6D90E130F857","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9dca263caa07d38983614105392b4b312118b0ba","datavalue":{"value":"10.1016/0095-8956(91)90059-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186126$B9E95C6C-EAC9-49A4-AFAD-8A089870A779","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d6aa4b6ea137743f1486f22cb13cc1976b208f6","datavalue":{"value":{"entity-type":"item","numeric-id":215010,"id":"Q215010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$3981DDF5-4284-4DCB-B64E-6BC3EFC31A78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5c81bf39e162601d4c36745779a6b8672aa2a934","datavalue":{"value":{"entity-type":"item","numeric-id":233193,"id":"Q233193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$36EFC368-58F7-48F3-BBA5-DDBB52040753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$757F8C08-C040-48A2-AD0F-EB2D3FBB4D47","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$D5EB2E1D-2C60-4A66-840F-EE503FD1146B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1186126$7C85361C-C7BE-4D19-BA2E-8C9FA1D4A9A7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"67c9836c6c1428dec57e693f0725eefb30ccfd89","datavalue":{"value":"The paper studies bipartite decompositions of graphs. A bipartite decomposition of a graph is a colouring of edges of \\(G\\) such that each colour class is the set of all edges of a complete bipartite subgraph of \\(G\\). Theorem 1 states that in any bipartite decomposition of \\(K_ n\\) there is a spanning tree of \\(K_ n\\), no two of whose edges have the same colour. This is a strengthening of a conjecture by D. de Caen. A more general theorem is Theorem 2 stating that if \\(G\\) is a graph with \\(p\\) positive and \\(q\\) negative eigenvalues, then in any bipartite decomposition of \\(G\\) there is a forest with \\(\\max\\{p,q\\}\\) edges, no two of which have the same colour. Further theorems bring similar results concerning near-trees and near-forests. A near-tree is an unicyclic graph having a circuit of odd length, a near-forest is a graph, all of whose connected components are near-trees. Also clique decompositions and matchings are studied.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186126$3C98D160-8079-47AD-909C-C1BA72A68221","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b462d071c33d7d83486f9fef57845bb41d7acf","datavalue":{"value":{"entity-type":"item","numeric-id":190573,"id":"Q190573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$92806D42-D5AF-4F7B-BAAE-550E52ECD841","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186126$CB59E600-9BCC-4BA7-8824-1BB9AD120D14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186126$6CA0505A-8B2E-4A57-BA3A-6D00B761A1F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186126$CA88D6B6-5698-48CC-BAF8-9BA42C05B48E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"80c36baea26f438a1dad13cfa00eac7a18baa50b","datavalue":{"value":"36236","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186126$5B58B652-45B5-4151-898F-5E7F1C8DB9D7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59e104fc9083dc8c4e491b340ba5128d82bfc9b1","datavalue":{"value":"colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186126$9F325AE3-7BD3-4A10-9D6D-71D71DFACF46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdfaf6cb47d1865beef1ea3fd0dd447ea44046db","datavalue":{"value":"bipartite decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186126$6D2A1595-3881-4852-8F26-1E14161B08D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186126$98FD431C-C3C5-4D0A-AAB5-22AE52C5D71D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc79eafc1d9ceb1ab79797a36449e9df369395df","datavalue":{"value":"forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186126$D9BF08F2-F523-4F1D-8BB2-88B33D6E09F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d7b571b0d2fa657be1f28c12e99e14c4c5d2218","datavalue":{"value":"near-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186126$1E988E00-2F6B-4EFA-B23B-A1B80807EF54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d8b25636fe59819bead267f6083683503a21e69","datavalue":{"value":"near-forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186126$B62857F8-1B60-44EA-B1C2-7749B91E1ACD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"45f7fe165a3bc3d090595842ffe8671268f74b9b","datavalue":{"value":"clique decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186126$075771F4-01C7-448E-A8A1-B38D8FD690BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f688ae621af73201a019c8f1194e5d3f579b7573","datavalue":{"value":"matchings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186126$A5D9BA2B-3D5C-40A7-B8CC-A7B6A5E6D627","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":"Q1186126$CB7E149C-DB95-43F3-8BD1-1740EF91EFDE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"824006286a76c1a013fb05fc0449644f816acb3e","datavalue":{"value":{"entity-type":"item","numeric-id":1821120,"id":"Q1821120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$C095E117-835F-4FBE-9EEB-D2F059D2ED85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ab2542fd41f36a17c4f1bd2f2cbeb6a41a4d0a1","datavalue":{"value":{"entity-type":"item","numeric-id":4723764,"id":"Q4723764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$2769274D-7AB7-419A-8736-563D8116C80E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82a9c8cc4cdcade87b9ccc515a00403d48d4459b","datavalue":{"value":{"entity-type":"item","numeric-id":5636776,"id":"Q5636776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$E6D05301-B8C1-4CE8-AF1E-D6EFF9277E46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddff6e8fb88b7da0c5291a5ba4d8da81cd77fd88","datavalue":{"value":{"entity-type":"item","numeric-id":5663904,"id":"Q5663904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$0295A9AF-6756-4427-8844-9B445EC0CF42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$5F90D236-E636-4CC4-A15A-F2B587B8112D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ce9c72fe3a0e8ae01215a77a81d6ba23d0db0a7","datavalue":{"value":{"entity-type":"item","numeric-id":789411,"id":"Q789411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$729C5AB7-46CA-407A-BF69-F23E6CC71E29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bef3ce047c7eb828a48fa89206a557b3aca45995","datavalue":{"value":{"entity-type":"item","numeric-id":5845425,"id":"Q5845425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$84513792-D84F-4B6D-8942-D8B4B3B36BFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6582283e06201cb94c8a5569364eddfab94c3ad1","datavalue":{"value":{"entity-type":"item","numeric-id":1217719,"id":"Q1217719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$3C7036CE-4861-4191-A615-5C7888219DFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9bb36bfa8ff9b999fd22009eb922d04862e30fb","datavalue":{"value":{"entity-type":"item","numeric-id":3967567,"id":"Q3967567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$E739939B-8E03-4145-B322-B93E4B2A8BCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186126$3AC9811A-B907-43A8-8E5A-A89AFDAF4CD0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1813cc44c061e477dd1f8c5d33944b5bbcaf06ee","datavalue":{"value":{"entity-type":"item","numeric-id":5948981,"id":"Q5948981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56f04b881782b7f65c83f42c0793f56c91a16e37","datavalue":{"value":{"amount":"+0.8129634857177734","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":"Q1186126$143B50EB-1A9D-44FC-A44F-491786C2E234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa3a9faa35278728b843fdbea7b4b59d7c259879","datavalue":{"value":{"entity-type":"item","numeric-id":4028276,"id":"Q4028276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"344542c58b0e0507afbec5f59ecfcec55f3123ce","datavalue":{"value":{"amount":"+0.8016089797019958","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":"Q1186126$A45FAE31-85DA-40E8-A865-202828D90C6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42ad90f27e0dd46c647102ddba483dd770804d7d","datavalue":{"value":{"entity-type":"item","numeric-id":1176735,"id":"Q1176735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3db3942a0fff016a416668f6b2c405d12d1bf0a","datavalue":{"value":{"amount":"+0.7973499894142151","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":"Q1186126$F0DAD438-9B12-4232-A025-AFE4795462B4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Multicolored forests in bipartite decompositions of graphs","badges":[]}}}}}