{"entities":{"Q6106299":{"pageid":13240606,"ns":120,"title":"Item:Q6106299","lastrevid":58698714,"modified":"2026-04-06T09:18:37Z","type":"item","id":"Q6106299","labels":{"en":{"language":"en","value":"Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7702598"}},"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":"Q6106299$377FF5EC-F17E-4172-9D57-AD30A02DA24B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"18105cc227fbd62813673fb922aeefa249b20ea3","datavalue":{"value":{"text":"Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6106299$0E8F2A4B-7A28-4791-A164-7666E3E4A138","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b932a993e93222d636399824eb6b38972d51ae87","datavalue":{"value":"1517.05121","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6106299$F551169C-EF32-49DF-A539-B34B7B83DEE8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"463063b92afa7a0f6c81a27d606b59935ddcd557","datavalue":{"value":"10.37236/11623","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6106299$DA0B30A3-971D-450E-B0DD-A8CCC67EEDA0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"694492fc4bfa63ad752ce97ad5a3225b46984eae","datavalue":{"value":{"entity-type":"item","numeric-id":2171015,"id":"Q2171015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$2DD3D91C-BD25-47CF-8773-881AA45033E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"86791d2de8f741697c1a28c841b5e520b1ea6f17","datavalue":{"value":{"entity-type":"item","numeric-id":256974,"id":"Q256974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$A018D766-367E-40AE-B131-8F2CAAB0986E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7305cbbed27371e443b6b7f834c85ebb75e60d5e","datavalue":{"value":{"entity-type":"item","numeric-id":2138960,"id":"Q2138960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$9CF12E78-63EA-410F-A0E5-359E9DC86F4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f84c2585906a3dfec8dc78c048cfc8b3b8be2285","datavalue":{"value":{"entity-type":"item","numeric-id":345122,"id":"Q345122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$D2E2CF80-FC2C-4BF7-AE9D-7D5E49B1AA02","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":"Q6106299$1927A437-A077-4EE4-A0E7-CAC53650CF55","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"52958a1a3302f5b699063490fddb5552c7118c47","datavalue":{"value":{"time":"+2023-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6106299$7C95F22A-2C28-4EB7-A396-CF3FF16F64A6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2c202b9f6b67d96f9bcb6f993fb655a4820ea9af","datavalue":{"value":"https://arxiv.org/abs/2203.06775","type":"string"},"datatype":"url"},"type":"statement","id":"Q6106299$FEFA8D5E-C7CC-4693-85A0-D2800308F7B6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0f287f1cb04bca39a0c11b90112ead6ca53ebce8","datavalue":{"value":"Summary: A hole in a graph \\(G\\) is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph \\(K_4\\) by removing an edge. A pyramid is a graph consisting of a vertex \\(a\\) called the apex and a triangle \\(\\{b_1, b_2, b_3\\}\\) called the base, and three paths \\(P_i\\) from \\(a\\) to \\(b_i\\) for \\(1 \\leqslant i \\leqslant 3\\), all of length at least one, such that for \\(i \\neq j\\), the only edge between \\(P_i \\setminus \\{a\\}\\) and \\(P_j \\setminus \\{a\\}\\) is \\(b_ib_j\\), and at most one of \\(P_1, P_2\\), and \\(P_3\\) has length exactly one. For a family \\(\\mathcal{H}\\) of graphs, we say a graph \\(G\\) is \\(\\mathcal{H}\\)-free if no induced subgraph of \\(G\\) is isomorphic to a member of \\(\\mathcal{H}\\). \\textit{K. Cameron} et al. [Discrete Math. 341, No. 2, 463--473 (2018; Zbl 1376.05132)] proved that (even hole, triangle)-free graphs have treewidth at most five, which motivates studying the treewidth of even-hole-free graphs of larger clique number. \\textit{N. L. D. Sintiari} and \\textit{N. Trotignon} [J. Graph Theory 97, No. 4, 475--509 (2021; \\url{DOI:10.1002/jgt.22666})] provided a construction of (even hole, pyramid, \\(K_4)\\)-free graphs of arbitrarily large treewidth. Here, we show that for every \\(t\\), (even hole, pyramid, diamond, \\(K_t)\\)-free graphs have bounded treewidth. The graphs constructed by Sintiari and Trotignon [loc. cit.] contain diamonds, so our result is sharp in the sense that it is false if we do not exclude diamonds. Our main result is in fact more general, that treewidth is bounded in graphs excluding certain wheels and three-path-configurations, diamonds, and a fixed complete graph. The proof uses ``non-crossing decompositions'' methods similar to those in previous papers in this series. In previous papers, however, bounded degree was a necessary condition to prove bounded treewidth. The result of this paper is the first to use the method of ``non-crossing decompositions'' to prove bounded treewidth in a graph class of unbounded maximum degree.  For Parts I--III see [the first author et al., J. Comb. Theory, Ser. B 157, 144--175 (2022; Zbl 1497.05179); ``Induced subgraphs and tree decompositions. II. Toward walls and their line graphs in graphs of bounded degree'', Preprint, \\url{arXiv:2108.01162}; ``Induced subgraphs and tree decompositions. III. Three-path-configurations and logarithmic treewidth'', Preprint, \\url{arXiv:2109.01310}].","type":"string"},"datatype":"string"},"type":"statement","id":"Q6106299$7584D8D8-03CF-4F2D-A3A0-AEF41F163F30","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6106299$4B4C852B-A8DA-41A8-867C-7A1B83CD498B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6106299$BF9DD799-D32B-4B5B-BBB8-56B53C1A3B90","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"655abc92234cef3586e7183db1eba628a5e0f55a","datavalue":{"value":"7702598","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6106299$1C9EFC5F-70E0-415E-8308-FBF4C74FCEFB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b68a5b9b70b09efeff70d1b56931a601600eb61","datavalue":{"value":"even-hole-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6106299$D1ECEE10-E855-46A0-AA61-9D720FA0DBEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8af2a2b5ba90d9cf2805e6a6fc80874ac1471660","datavalue":{"value":"structure theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6106299$3498DC8F-7DF9-42CD-ACCE-C58CE92E0826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q6106299$698454E3-74E5-4EF5-91C6-13CBD71D5D3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q6106299$6B2E7514-D239-4601-B5C3-F0BCB5457D94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q6106299$06852DDF-4140-459B-8278-7A1BA28B47C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2e82f2d9c5ffd04f0380d3795553cbed4c2e58c","datavalue":{"value":"maximum weight stable set","type":"string"},"datatype":"string"},"type":"statement","id":"Q6106299$F4D9BDB3-5461-4D40-974A-203DDEDF3754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q6106299$A661ADA5-C534-427B-9ECF-4D4466C11E40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5eb03826ecb9d862c3a8c13a3c8eb36c4bc27ecd","datavalue":{"value":"clique-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q6106299$E1B592C8-050B-4CB3-B558-30C0A81EEBC0","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":"Q6106299$CDF77CE9-8BFA-43EF-B639-DC6F6AD7D2B4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d47e7196995b29a9242f35a22b9e4ab59fd9a289","datavalue":{"value":"W4380990053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6106299$DF7B8304-FD9F-406B-A412-7CCE4A99F882","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bc618db23017ff1d9c04e797e69cca6560a6253","datavalue":{"value":{"entity-type":"item","numeric-id":1979431,"id":"Q1979431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$67C6388A-18DF-4D91-97EC-674E2B556A43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad58bbabf51f3eae35513d75485e6efb5be6bb63","datavalue":{"value":{"entity-type":"item","numeric-id":2171016,"id":"Q2171016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$EB8345BA-9BE3-43EB-AAFA-1F4F07F51B26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05ba062e35f5b9f4b7072a7b25dd2ea1a17ea1d6","datavalue":{"value":{"entity-type":"item","numeric-id":3795218,"id":"Q3795218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$D7A44A25-6300-4131-86F3-CA703B4A47AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7033f613f87271bbae4d15c33caa982a0486ba8","datavalue":{"value":{"entity-type":"item","numeric-id":819825,"id":"Q819825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$E7330CDA-3D55-403C-B15C-9BA455853E5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e6fc3badc87618cc9eab249bee010e0aa6fadca","datavalue":{"value":{"entity-type":"item","numeric-id":1685999,"id":"Q1685999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$56580487-B951-4CEC-884D-6471A4908CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08cc9cdd9999a46859ae4f667ab34baac016718b","datavalue":{"value":{"entity-type":"item","numeric-id":5502162,"id":"Q5502162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$BDED88E6-52DC-484C-BE50-8101DB5A8501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"911589c443d66de910231040cb752d7897658c23","datavalue":{"value":{"entity-type":"item","numeric-id":1932477,"id":"Q1932477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$6295B07A-2E1E-402A-AB0B-F3C8579F4502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5dc42a680b8ef6292b67bd3175f40575a5cbf46","datavalue":{"value":{"entity-type":"item","numeric-id":2978180,"id":"Q2978180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$9D1B702F-B10F-4896-B968-9E4B8D1F5CE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c69d431de8a249a0cea53fc9de8100dff5d12a72","datavalue":{"value":{"entity-type":"item","numeric-id":2692786,"id":"Q2692786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$E72B5EEE-DD5B-4A08-9B51-64D39B600774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"189ba0ee8b34b66fe9f7ad584bcd68efc6058193","datavalue":{"value":{"entity-type":"item","numeric-id":705743,"id":"Q705743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$994DEEE6-637A-4DBD-A95B-444DBF38C4BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56be2ccfc66fe28b96bcac3fc20ce2397ee8326c","datavalue":{"value":{"entity-type":"item","numeric-id":444381,"id":"Q444381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$00985F72-4EB3-4FF9-8FC7-4C53F7395B4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c0f6dd793166a567719b2fb5d958eb883aea03d","datavalue":{"value":{"entity-type":"item","numeric-id":1079583,"id":"Q1079583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$9F6D7C0E-D0C9-4159-ABD2-5D9C0D87C7FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cb66d8bb21cd38566dc6ce4a04832b4ee95a502","datavalue":{"value":{"entity-type":"item","numeric-id":6080861,"id":"Q6080861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$D108DAB5-EE33-431D-B629-05DAA080BD67","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5786db1ccbe637b57bd1d8008f9491ca03b1be1e","datavalue":{"value":{"entity-type":"item","numeric-id":6080868,"id":"Q6080868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"781634aa8cdca16b7669d14df1c4f4f530cf35c6","datavalue":{"value":{"amount":"+0.8658294677734375","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":"Q6106299$47C48C4A-3F98-4E46-89C9-22E6AD601C79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e35e68a748f8b3071324000ba5bad5b254a33213","datavalue":{"value":{"entity-type":"item","numeric-id":6080861,"id":"Q6080861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0183aadf038851330b182e4f2ad3d708ff88f717","datavalue":{"value":{"amount":"+0.8619353175163269","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":"Q6106299$79AB9D9A-296B-46F3-A188-597776653E62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b03a8bcd6ec4a6000eb5498400a842946cda4263","datavalue":{"value":{"entity-type":"item","numeric-id":1979431,"id":"Q1979431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b6906fb5ef8092ff6724c8fed66d3df76b07a5d","datavalue":{"value":{"amount":"+0.8006945848464966","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":"Q6106299$F921E430-1A5E-4833-A76A-43820EB6C9D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96e55a2992eecbe61f6740e6cac5e5eb325b9073","datavalue":{"value":{"entity-type":"item","numeric-id":2171016,"id":"Q2171016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a65890e627ea251312178ee173702c41b636b06","datavalue":{"value":{"amount":"+0.7855635285377502","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":"Q6106299$3CC43EE8-742C-4CB4-A1AC-FE53FBBA88AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de74782d0b7a1d5c467df5ace372f9303332161a","datavalue":{"value":{"entity-type":"item","numeric-id":1026014,"id":"Q1026014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c624cc3831003a01692560f57b1df8d13de5e8d","datavalue":{"value":{"amount":"+0.7744038701057434","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":"Q6106299$D93B8C31-EC83-4E47-AF8C-5DC21B579B08","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6106299$9B41C027-EC6B-4317-9D5C-A708F8A4C731","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6106299","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6106299"}}}}}