{"entities":{"Q1010820":{"pageid":1012668,"ns":120,"title":"Item:Q1010820","lastrevid":66595134,"modified":"2026-04-12T11:11:08Z","type":"item","id":"Q1010820","labels":{"en":{"language":"en","value":"Tree-thickness and caterpillar-thickness under girth constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540998"}},"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":"Q1010820$A7308AB7-9ED5-4F41-B8AD-5211AEA9774A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fb8d5d07feaea28466e4df9d521b7e7db994a030","datavalue":{"value":{"text":"Tree-thickness and caterpillar-thickness under girth constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010820$5F60F17C-109D-40DA-A9EA-26F54E156B2D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f02ef0291a1fee0862f3c7309c513d00088a4d86","datavalue":{"value":"1163.05321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010820$472C7985-7561-4FA3-BBA6-B50E61FCA46E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"67c2ecae7a3817dac74fc1e587d9b66bbe585b92","datavalue":{"value":{"entity-type":"item","numeric-id":466857,"id":"Q466857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010820$26F4A5E0-B86C-461D-B473-88571342C102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d4c73f0a1fcfa77f8c56f84fd9c0566fb0d581","datavalue":{"value":{"entity-type":"item","numeric-id":185079,"id":"Q185079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010820$13265559-A2B2-4A70-AFE5-A39FBD314D4A","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":"Q1010820$C41FE447-0277-457F-A6A0-2AB6D5543DFA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010820$28E82138-CAD7-4314-8DCA-3AF2386582CC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"40662b3641cb1e56c1d525e51c55fb22dee47559","datavalue":{"value":"https://eudml.org/doc/129981","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010820$D1BFC3C0-A9FB-4208-BA63-A315E934FFFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"263b0ebe148e48cf813dad3ca5c1e3cf4051a196","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r93.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010820$4BEA6649-F964-437F-BF14-14F721036D02","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ac2cf96b8929c3770fa1500d4c57755873cb9e8","datavalue":{"value":"Summary: We study extremal problems for decomposing a connected \\(n\\)-vertex graph \\(G\\) into trees or into caterpillars. The least size of such a decomposition is the tree thickness \\(\\theta_{\\mathbf T}(G)\\) or caterpillar thickness \\(\\theta_{\\mathbf C}(G)\\). If \\(G\\) has girth \\(g\\) with \\(g\\geq 5\\), then \\(\\theta_{\\mathbf T}(G)\\leq \\lfloor{n/g}\\rfloor+1\\). We conjecture that the bound holds also for \\(g=4\\) and prove it when \\(G\\) contains no subdivision of \\(K_{2,3}\\) with girth 4. For \\(\\theta_{\\mathbf C}\\), we prove that \\(\\theta_{\\mathbf C}(G)\\leq\\lceil{(n-2)/4}\\rceil\\) when \\(G\\) has girth at least 6 and is not a 6-cycle. For triangle-free graphs, we conjecture that \\(\\theta_{\\mathbf C}(G)\\leq\\lceil{3n/8}\\rceil\\) and prove it for outerplanar graphs. For 2-connected graphs with girth \\(g\\), we conjecture that \\(\\theta_{\\mathbf C}(G)\\leq \\lfloor{n/g}\\rfloor\\) when \\(n\\geq\\max\\{6,g^2/2\\}\\) and prove it for outerplanar graphs. All the bounds are sharp (sharpness in the \\(\\lceil{3n/8}\\rceil\\) bound is shown only for \\(n\\equiv 5 \\mod 8\\)).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010820$856C504F-2DAA-4A76-9AB6-20584D62C990","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010820$0B4D28C2-8130-44DD-B185-F6F5C141AD0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010820$01309267-D18A-4C56-9C6F-E8DE7F09AAFF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c2bd822678d2d021bf4cdbf847c221a25e1c3816","datavalue":{"value":"5540998","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010820$FF6438B6-E19A-453E-ADCC-9C75643EEEA2","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":"Q1010820$82D15609-9E25-494B-A946-4784E3D62EF3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"9b52fb852762e2f566e8eded45d53afaa022e9fd","datavalue":{"value":"bafkreigdyykfnb4sjiny4aboyviygtdkwtwdi4ycvhrgo3ydovsb5h7vlq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010820$5D46DBD0-B4CD-44E5-8480-8B7249B15637","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e76e71faa9cbb8cbdae1195a6eef093b6a8398e","datavalue":{"value":{"entity-type":"item","numeric-id":580352,"id":"Q580352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e426de40ed556c688311429a5bc1b4c8d445c9f","datavalue":{"value":{"amount":"+0.8086104989051819","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":"Q1010820$371AEBAE-CB3D-4348-BA6C-609E8C5F985E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b2ca15800703407f6e50986b988c5ba5fbd8bb0","datavalue":{"value":{"entity-type":"item","numeric-id":3835473,"id":"Q3835473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df45cac9eb11c2f7a2913149bba79142762123bc","datavalue":{"value":{"amount":"+0.7618588805198669","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":"Q1010820$2E1751E1-6728-41AF-AD28-34477B069ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5246c16ccaddaec00a4f82d51b7fc7f580acafc1","datavalue":{"value":{"entity-type":"item","numeric-id":345073,"id":"Q345073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d53b291c9981aa9bdcacbb9eaf6f7123516c2e1f","datavalue":{"value":{"amount":"+0.7419171333312988","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":"Q1010820$DD72FD32-D7A4-4A44-8005-6F8E5A050729","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21fb9b486c5027b84c24ef9551993281afa724a6","datavalue":{"value":{"entity-type":"item","numeric-id":765188,"id":"Q765188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84223e8e939565f8ed2d5db3d893158888367177","datavalue":{"value":{"amount":"+0.7357516884803772","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":"Q1010820$90170F67-41C2-468A-B503-74901707F13D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61a4c0563f503e21b4efddff9505b44a26663ae2","datavalue":{"value":{"entity-type":"item","numeric-id":2138955,"id":"Q2138955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be735abcdc3cde4ae4719aa09f10b5a46948e402","datavalue":{"value":{"amount":"+0.7348923683166504","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":"Q1010820$1A35DABC-A484-4FFF-B077-0D804436BE03","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tree-thickness and caterpillar-thickness under girth constraints","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tree-thickness_and_caterpillar-thickness_under_girth_constraints"}}}}}