{"entities":{"Q849635":{"pageid":851483,"ns":120,"title":"Item:Q849635","lastrevid":64812153,"modified":"2026-04-11T22:23:39Z","type":"item","id":"Q849635","labels":{"en":{"language":"en","value":"Dense trees: a new look at degenerate graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5069050"}},"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":"Q849635$182E9941-E3FF-400E-AF1D-9F4BC10D5DDA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"831bc85279943a71e69548fb82e9d5b32af48ddc","datavalue":{"value":{"text":"Dense trees: a new look at degenerate graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q849635$7733408C-4C2F-428B-A4EB-BE20CBD8EFF5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c51cc9811c5305e8d8ae5d17f7a1707b870ae2b","datavalue":{"value":"1103.05085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849635$97AA1E9B-0EB8-40D1-8DDF-2A79408C6D69","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"962105247e46dc6bb2a899a58d55166a0d345568","datavalue":{"value":{"entity-type":"item","numeric-id":598253,"id":"Q598253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$55D47535-AE9C-4CB1-A3E6-E5EFFBBE64C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1347b4a3ccb2c82315cb5da7defbc0e54a737694","datavalue":{"value":{"entity-type":"item","numeric-id":287200,"id":"Q287200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$64DB1BB1-F495-49DE-AC6C-9EE1CD15F7CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c2105ccd2a2cc177eb70ff294931e27b6c4ed34","datavalue":{"value":{"entity-type":"item","numeric-id":287201,"id":"Q287201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$E7B55086-71D3-467C-AC6E-7669F4DCEE88","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0a33251796f18919242eb286ef1f888e5d6e79da","datavalue":{"value":{"entity-type":"item","numeric-id":350720,"id":"Q350720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$84A0F254-F84A-4104-B7E1-077CCA928CCE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e652df40e88a7517140c29fd3339f7b3a9de3e3d","datavalue":{"value":{"time":"+2006-10-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q849635$C130FADD-1D2B-4683-8305-0D1BB77C7DDA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ca7579454920ae3c1960a4d4e9c514b7104bc267","datavalue":{"value":"A \\(k\\)-dense forest (tree) is a (connected) graph of which each subgraph contains a vertex of degree at most \\(k\\). That is, the \\(1\\)-dense trees are exactly the trees, and all partial \\(k\\)-trees are \\(k\\)-dense forests, see \\textit{H. L. Bodlaender} [Theor.\\ Comput.\\ Sci.\\ 209, 1--45 (1998; Zbl 0912.68148)]. \\(k\\)-dense trees were studied in connection with first-fit colouring by \\textit{G. Szekeres} and \\textit{H. S. Wilf} [J.\\ Comb.\\ Theory 4, 1--3 (1967; Zbl 0171.44901)] and \\textit{D. W. Matula} [SIAM Rev.\\ 10, 481--482 (1968)], and also by \\textit{D. R. Lick} and \\textit{A. T. White} [Can.\\ J.\\ Math.\\ 22, 1082--1096 (1970; Zbl 0202.23502)], who called them \\(k\\)-degenerate graphs, and by \\textit{E. C. Freuder} [J.\\ Assoc.\\ Comput.\\ Mach.\\ 29, 24--32 (1982; Zbl 0477.68063)]. Here the focus is on maximal \\(k\\)-dense trees, their relation to \\(k\\)-trees, and the decomposition of \\(k\\)-dense trees into \\(k\\)-spanning trees.","type":"string"},"datatype":"string"},"type":"statement","id":"Q849635$D4FD890B-F143-4868-90C0-AF54CAEC7E9C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849635$544A39B7-81A1-47D3-8AAD-651A703734C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849635$DEAD6B9B-B23B-4682-B25A-7D63BC27FAC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849635$D5AFDFA0-8447-4B08-B188-3D959348A9E8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7f0601fa66f8b522b0a4779e77503c695abbc24f","datavalue":{"value":"5069050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849635$1A769A14-32C1-4CE8-8B27-ECDCE8AC542B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e179bd6920250386da0119e0f96c8172abf9a4f7","datavalue":{"value":"\\(k\\)-dense tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q849635$042CB9D2-0F86-4483-BDF3-ADF62951A978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2753fd164328a0a9efa1a63fe1a06da0e4efcfe7","datavalue":{"value":"\\(k\\)-dense forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q849635$331EAC0D-95A4-44D7-93AB-72E47C9727C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e71e93721c383463b8f8fb8816dacb234eccc3bc","datavalue":{"value":"\\(k\\)-elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q849635$FEC4AF77-73E9-42E5-8837-E491F31BFBDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf93f082a91a712924057cec95f47b5382c4c672","datavalue":{"value":"\\(k\\)-degenerate graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q849635$89EE6507-6A62-4C53-B291-28F2EC748AB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211a09b137bdf42f268c86e50a34a0d25fd19aa0","datavalue":{"value":"partial \\(k\\)-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q849635$D01B37D2-D586-44A2-AB55-D30BF252D996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q849635$3081DC74-6712-4243-85A2-1AA683D8BF7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q849635$7CFA71DA-8B48-4117-BB29-F3DB81B19D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q849635$CD5B95F0-D8BB-49BA-9FEC-4ED147AA87A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44b4a0255e2a5894ff8b38a31886419ea6ecb577","datavalue":{"value":"interconnecting structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q849635$B40BB1A0-A033-4355-A4E6-D1DB7A3A59F2","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":"Q849635$BAD85DEF-4CC7-43DC-BA21-E5C930678F25","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"93b1fc52e2c6102dff4b6879800df3f97a3b0bb0","datavalue":{"value":"https://doi.org/10.1016/j.jda.2005.12.008","type":"string"},"datatype":"url"},"type":"statement","id":"Q849635$4E1FB742-6B39-4406-827E-E76BC52FDE23","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"736f491062de78311d0acc933deea0e3ed03a013","datavalue":{"value":"W2063493837","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849635$C37FA967-E7DE-4E4A-BCC8-366301A7F2F2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4b64bfe898c7e488d66acca23dcc473e8ce5ef2","datavalue":{"value":{"entity-type":"item","numeric-id":1962049,"id":"Q1962049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$68A52314-EA7C-4E8A-9A73-C572268D0FE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57515aea1ad564d767f2a1d2b4fdb04b8bf50ff4","datavalue":{"value":{"entity-type":"item","numeric-id":1274912,"id":"Q1274912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$82E82FAB-DC2F-42F9-9B8B-C8367975D9C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41ab95cfd69e10430c9e72fb53fae7f5a4250a3f","datavalue":{"value":{"entity-type":"item","numeric-id":4947393,"id":"Q4947393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$4EBF79D3-830C-4FA8-8086-1CA3802D5D62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df1958ff7e040b608ab81be40fc268247c86c0f1","datavalue":{"value":{"entity-type":"item","numeric-id":3933756,"id":"Q3933756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$96435F53-CAF9-465C-A98C-42F16045E65A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$7DF8C8D5-E53E-4F68-B264-260D3BB7C376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3a0d4c2b83e2d1c052c87c581c72cdba8da38e3","datavalue":{"value":{"entity-type":"item","numeric-id":1338451,"id":"Q1338451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$D3EE1C70-CF39-4A2D-BE08-AE7352AC29DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef1e280ff313784cce95cf1dc6e1b139af0e3310","datavalue":{"value":{"entity-type":"item","numeric-id":5599569,"id":"Q5599569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$E1D9C625-1265-41E1-B79C-8285AE57F811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bdff9369cba0fd3674a39d854beb14e58a55bb2","datavalue":{"value":{"entity-type":"item","numeric-id":1566374,"id":"Q1566374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$8C048E00-7622-4565-AD9A-CB0D67888ACB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c1bb97e5aa8cede73a154b925bb1362eeb78ef7","datavalue":{"value":{"entity-type":"item","numeric-id":5558479,"id":"Q5558479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q849635$D418D0DC-0CEE-4D79-981A-D4C88F5D2D96","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7672e60784f027e64ad356d6d52ed906d32e96a5","datavalue":{"value":"10.1016/J.JDA.2005.12.008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q849635$C5A98894-B62B-4C48-A202-64652DF2F626","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59ae38f5ac835727902caaa99fc409093285a654","datavalue":{"value":{"entity-type":"item","numeric-id":2866413,"id":"Q2866413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"824b7a52d8ed26323c8c5c81f889f24d164c4b86","datavalue":{"value":{"amount":"+0.771661102771759","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":"Q849635$1036BDED-F09E-46C4-8F9F-ED86F55EBA12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f876bbc36fbdcfc7fb8c1c85e896b68a00ca467","datavalue":{"value":{"entity-type":"item","numeric-id":497365,"id":"Q497365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98285e5b834fce542354990f16e138ae3da54d44","datavalue":{"value":{"amount":"+0.7709975838661194","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":"Q849635$7083DF78-73B2-46A5-B7CE-44ED082917A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78609153852148effc1918bdb55cc35bdebd4bbd","datavalue":{"value":{"entity-type":"item","numeric-id":1324448,"id":"Q1324448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0bf2651a1d35c6677a1ed9279fc9eee3772cca8","datavalue":{"value":{"amount":"+0.7598182559013367","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":"Q849635$B3DF25B6-7EB3-490C-878F-199154BD9F3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1b63eb3bf719f31cdeed19a6bc50a08dad8aa61","datavalue":{"value":{"entity-type":"item","numeric-id":5046563,"id":"Q5046563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8d55e28df74d638388e0461549347cf103ab0e6","datavalue":{"value":{"amount":"+0.7577235102653503","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":"Q849635$9E190434-B842-4BD2-9743-117BBAB2D8B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f62f76f8aad86dd2cb47fa41a2aa852d446d321","datavalue":{"value":{"entity-type":"item","numeric-id":3140349,"id":"Q3140349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8da87f11633ae4f1a46ed4ec014df90d910a146f","datavalue":{"value":{"amount":"+0.7557258605957031","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":"Q849635$6473E4AC-42EE-4D65-BD85-75E3F4E69C7D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Dense trees: a new look at degenerate graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Dense_trees:_a_new_look_at_degenerate_graphs"}}}}}