{"entities":{"Q396879":{"pageid":398646,"ns":120,"title":"Item:Q396879","lastrevid":61622115,"modified":"2026-04-11T00:32:32Z","type":"item","id":"Q396879","labels":{"en":{"language":"en","value":"Product dimension of forests and bounded treewidth graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6330314"}},"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":"Q396879$B05459DC-F0D0-4097-9FDF-A4019F365C96","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cb3c3ac7b9b627fe3199dada60fe14b164404e37","datavalue":{"value":{"text":"Product dimension of forests and bounded treewidth graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q396879$CCF76FCC-A33D-4336-96A5-A3892727F632","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4262ddc7cd0a09fe54dde14f389929eabcb0c82e","datavalue":{"value":"1295.05077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396879$2EE110E9-9713-422C-9DD5-22E9E2FBBF1F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"abcd67b883bdb135fa3e2d4d00b0f0c8f6d98bc4","datavalue":{"value":{"entity-type":"item","numeric-id":300471,"id":"Q300471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$453EDB87-9E17-40AB-983D-DBC21FEA0434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f39a90f713dbdf70d5bc8b33df7f3270a8d73566","datavalue":{"value":{"entity-type":"item","numeric-id":300472,"id":"Q300472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$4FCE1A8B-73D1-439F-82F5-8FC2E0A279E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"58e242255041fcc36cc5d243c0bca45de04a62e9","datavalue":{"value":{"entity-type":"item","numeric-id":300473,"id":"Q300473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$A620AD32-E8A3-4658-84DE-02F0563BC8E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c1429ecd5d8933d02560447c8bfa25625b854f14","datavalue":{"value":{"entity-type":"item","numeric-id":396878,"id":"Q396878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$3F15E199-4774-40B0-A057-0905289F9F62","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":"Q396879$383C7A93-5D24-4B07-A319-0544E4D7843D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"014386d1e7349618004d8e2aa9650d7520cb60bd","datavalue":{"value":{"time":"+2014-08-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q396879$5ED00BB8-80BB-436F-BBD4-A0B31E336D41","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8ee280f741da75ddb17693824623c002a8ce60ec","datavalue":{"value":"https://arxiv.org/abs/1209.2218","type":"string"},"datatype":"url"},"type":"statement","id":"Q396879$DFB91004-3874-4C89-ADB7-75AA24A9BDBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"e99781a4dc03161376b4db0522d33fecf8085b4b","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p42","type":"string"},"datatype":"url"},"type":"statement","id":"Q396879$1A0F6252-6496-409C-8FEC-FE96183588B0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa89875a5a5a670971ce823cbe5ef360e3e88e87","datavalue":{"value":"Summary: The product dimension of a graph \\(G\\) is defined as the minimum natural number \\(l\\) such that \\(G\\) is an induced subgraph of a direct product of \\(l\\) complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and \\(k\\)-degenerate graphs. We show that every forest on \\(n\\) vertices has product dimension at most \\(1.441 \\log n + 3\\). This improves the best known upper bound of \\(3 \\log n\\) for the same due to \\textit{S. Poljak} and \\textit{A. Pultr} [Discrete Math. 34, 165--171 (1981; Zbl 0476.05075)]. The technique used in arriving at the above bound is extended and combined with a well-known result on the existence of orthogonal Latin squares to show that every graph on \\(n\\) vertices with treewidth at most \\(t\\) has product dimension at most \\((t+2)(\\log n + 1)\\). We also show that every \\(k\\)-degenerate graph on \\(n\\) vertices has product dimension at most \\(\\lceil 5.545 k \\log n \\rceil + 1\\). This improves the upper bound of \\(32 k \\log n\\) for the same by \\textit{N. Eaton} and \\textit{V. R\u00f6dl} [Combinatorica 16, No. 1, 59--85 (1996; Zbl 0853.05049)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q396879$63F05631-BCD9-48BB-8D59-9F23958262BC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396879$57567C4F-ACD6-410D-991F-5F752B06C4CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396879$10D0670D-6480-4EE6-8865-7618AE08F80E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1186c24bc5f2e826b92dfa1f9e766c44f30b10ba","datavalue":{"value":"6330314","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396879$DD9F0376-0820-487E-B938-39255116E712","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0564320e7e49fa8d06f16e831b755daeab902714","datavalue":{"value":"product dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q396879$69F8FFF7-2C29-416E-BF84-E977CFE00984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ffd3fdce3fa1dfd72447a2428ba56b183c98dd5","datavalue":{"value":"representation number","type":"string"},"datatype":"string"},"type":"statement","id":"Q396879$8B622A61-A30C-4E85-99B8-9C46723848E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc79eafc1d9ceb1ab79797a36449e9df369395df","datavalue":{"value":"forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q396879$2820A5B6-046D-49E5-ABBE-AA907A370F9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"538c448551d614886ff4d945bbebfe9b3e1e1279","datavalue":{"value":"bounded treewidth graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q396879$3EE7E98C-89E5-49CB-AB27-C74224FCD7D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff0c8740d26fe24e2c3077469ce65da3317d552d","datavalue":{"value":"k-degenerate graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q396879$3C39AACF-4AD7-4C87-9273-2B433964ED9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8de1b9e7af67e79ff247e2a0d45279f4c6ad8a45","datavalue":{"value":"orthogonal Latin squares","type":"string"},"datatype":"string"},"type":"statement","id":"Q396879$1471470D-A2C1-40A1-A2F8-2E90B9B282EB","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":"Q396879$75BF8D75-B983-44F8-87F8-F73EE0A702E0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"01fc7ea5842e9b1b6440ec7e606e39ca7e6a2dd8","datavalue":{"value":{"entity-type":"item","numeric-id":3784111,"id":"Q3784111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$205B6404-057C-470D-9767-37E474D4B560","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38abbb7b2b127989284f046dab850c1b2781022d","datavalue":{"value":{"entity-type":"item","numeric-id":1103644,"id":"Q1103644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$ACDF185E-9C7C-4E84-B223-1F5D7CB7CC37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c0efd8ba1b2b55b1b279c691057d59f5b4a5bd8","datavalue":{"value":{"entity-type":"item","numeric-id":3270188,"id":"Q3270188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$BDA3BBED-C2A7-4DC7-9859-924BE7BE8D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f93b959a40c01f0b60bfc5059fb4ad571a44e8b2","datavalue":{"value":{"entity-type":"item","numeric-id":2642011,"id":"Q2642011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$C0AE43FE-6988-4AE7-9788-FCEBE9984534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dafb926bd57e90af567970236a3626398b86842","datavalue":{"value":{"entity-type":"item","numeric-id":1912752,"id":"Q1912752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$EEB67906-F775-4C6D-A171-C8D936982843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df8806f3add754f4b17eaae43400606bf1542372","datavalue":{"value":{"entity-type":"item","numeric-id":3032306,"id":"Q3032306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$8D5743FB-BAAE-403F-A4A0-BBF001B9BD8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30aaacdb9c20ab958dde738cf6545c6ad2ece39f","datavalue":{"value":{"entity-type":"item","numeric-id":870985,"id":"Q870985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$E53F7676-39A4-4D50-8E2A-47AD7BAFBC05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"271c811a336aff800357e976bb56e14118b58d1c","datavalue":{"value":{"entity-type":"item","numeric-id":1587599,"id":"Q1587599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$F96DA78E-1CE3-4D6D-A57E-E76E966C36FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"793645c9828dd2552ea795bd02cea4f87a3992af","datavalue":{"value":{"entity-type":"item","numeric-id":1142231,"id":"Q1142231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$DF1AA605-E6BF-4A1C-B7F5-1D741FCABFCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab7f069b12e7ff606d8b83aa6ad74fe061b7d80","datavalue":{"value":{"entity-type":"item","numeric-id":5453875,"id":"Q5453875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$D482FAA9-47E7-484A-8EEC-B7E589ED6129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77141351513f903c3a254e63b92ba0aa7b5d0160","datavalue":{"value":{"entity-type":"item","numeric-id":1250115,"id":"Q1250115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$1917399D-57D9-4838-9818-35BE53B85A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88736c0c3849b735292bf8f4b24ebaced51e296e","datavalue":{"value":{"entity-type":"item","numeric-id":5904988,"id":"Q5904988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396879$44AC52AE-E6E8-4EC8-942E-868DF1BA2EA1","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ed85005de015c4b83024bfa19d16a0582df8800e","datavalue":{"value":"bafkreihop4avo56crfyeejqoybzmfsn5rc4zmrtsqv2ip2gpfgpbyksiwy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396879$81ACC3C9-9E60-4C56-B45A-5D94CF73B3C8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b872bfde60d449aa27dd1500b4faf763e2a53aa2","datavalue":{"value":{"entity-type":"item","numeric-id":3737466,"id":"Q3737466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a794492ad1bd343ef624003c666f51723cb1d45","datavalue":{"value":{"amount":"+0.7596701383590698","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":"Q396879$C434ECC6-CC15-453A-9967-02201963C2BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1aa5a1bda5e82c440f0e6bf6af1e4c0f36e45215","datavalue":{"value":{"entity-type":"item","numeric-id":396918,"id":"Q396918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79911e2db070c2dacf24c9fdba0c37c83bf7985e","datavalue":{"value":{"amount":"+0.7449609041213989","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":"Q396879$64F9FDB8-0DD7-4605-B5AE-7A1B52DFE11F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a34d73acd92f402752d4bf4237857111238d574e","datavalue":{"value":{"entity-type":"item","numeric-id":2683145,"id":"Q2683145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d62213127db655d115a97aca6eace2ebf82280d7","datavalue":{"value":{"amount":"+0.7448925375938416","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":"Q396879$6536B984-2CA9-445F-A238-5949DA73FEDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e1240e4d2a975654cc20554c63e2961db6a6439","datavalue":{"value":{"entity-type":"item","numeric-id":6343705,"id":"Q6343705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a228a988f939fd39cfdb4195909f0b071d67b46a","datavalue":{"value":{"amount":"+0.7401782870292664","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":"Q396879$04BA24DC-12A1-4EEE-9207-AD11A47190C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3e9e68868dc7f3bc23fbac669308da4f8904b56","datavalue":{"value":{"entity-type":"item","numeric-id":5319301,"id":"Q5319301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83faaf84aebf7747d116aa17847a16b24c972c13","datavalue":{"value":{"amount":"+0.7352527379989624","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":"Q396879$A45E17F0-E742-4F1D-848C-EC2131A46993","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Product dimension of forests and bounded treewidth graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Product_dimension_of_forests_and_bounded_treewidth_graphs"}}}}}