{"entities":{"Q5939925":{"pageid":8116727,"ns":120,"title":"Item:Q5939925","lastrevid":47645398,"modified":"2026-01-02T07:27:47Z","type":"item","id":"Q5939925","labels":{"en":{"language":"en","value":"Tree width and regular triangulations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1623462"}},"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":"Q5939925$B3C874A5-BCC2-4497-AC0F-36B1D215B227","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6a1ad07888527d793fa20d1818fb829ad0ff7169","datavalue":{"value":{"text":"Tree width and regular triangulations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5939925$FD767A77-AB12-49F6-B170-5B801B8D01AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"78c09c25d7a0ac6b99e6bc2c2818ebfd6d6b8d1a","datavalue":{"value":"0973.05068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939925$CC4ADA97-F8C3-4E9E-B9B9-82C2374F3929","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"26f7d146467eabc1311e339a06aa332b70bef3b2","datavalue":{"value":"10.1016/S0012-365X(00)00102-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939925$DF09D1D7-FFE6-448C-BEFC-0CF9255230D2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a58b3a5be3b06a056c2a02a0f20493f73a30ac94","datavalue":{"value":{"entity-type":"item","numeric-id":765199,"id":"Q765199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939925$7BC16498-3508-4023-BDC0-0FA4B767503D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939925$54BD9218-8E30-4139-9695-F4A41A3769C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5c5332c48de08b7b8da8f565721b384b6d4a11a4","datavalue":{"value":{"time":"+2001-11-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":"Q5939925$393164CB-0CB4-4EFB-AFC1-46657FFD80BB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"94626be276206b45b57e94a7e29516fb1870dd91","datavalue":{"value":{"entity-type":"item","numeric-id":190550,"id":"Q190550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939925$92AE46BC-A00B-417F-BCCB-EDAAE16D5B7A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939925$F71EFD51-5DA8-489A-8CC3-9AE774D824FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939925$D10309DB-445D-4F1A-B119-A66428F7B415","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939925$CBA66CD4-70AD-449E-A5A9-4E1358EF6251","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"45b01fc3ca15af577ceab584abedf5202b847e58","datavalue":{"value":"1623462","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939925$A7C7C08F-C4B5-45B1-8E31-D63F8A9C1DFF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b17e6e28d1a18f7a35b77cc1e7558e6f62021227","datavalue":{"value":"tree width","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939925$A58E9258-DCF2-42C7-914D-78EB52EAABE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4495258d1cccdbb7c9e20a4f49387fdd97ef5796","datavalue":{"value":"Colin de Verdi\u00e8re number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939925$6FA128F3-6A99-4E36-93F2-2FAC8D5A0FF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9139df7b92a0dae0699c42013a432a7d68b3883","datavalue":{"value":"forbidden minor","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939925$5C5B8B9B-BAB4-4B69-A0F5-77F6A8C2CB2E","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":"Q5939925$DD74033C-AB80-490B-8088-62C8F97EFFD5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e24fad7cd83a2908338b97bd3d3d98266adb71f0","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00102-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q5939925$862B0266-8147-499F-AE03-DAF13F4E0D90","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d1ea81ce4a309fbc3d9db272be1f378de6fb491f","datavalue":{"value":"W2075173346","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939925$4A3A5382-5D35-4B53-98C4-32B473CD6088","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c338b6af7f396e8a503f2d43f745655a1ce997fd","datavalue":{"value":"In \\textit{Y. Colin de Verdi\u00e8re} [Multiplicities of eigenvalues and tree-width of graphs, J. Comb. Theory, Ser. B 74, 121-146 (1998; Zbl 1027.05064)] the following two definitions are introduced. The family \\(\\{\\Delta_k\\mid k\\geq 2\\}\\) of graphs is defined as follows. Subdivide each side of an equilateral triangle, \\(S\\), into \\(k-1\\) equal segments. Through the subdivision points, plot the lines parallel to the sides of \\(S\\). This induces a triangulation of \\(S\\) into \\((k-1)^2\\) congruent triangles. Now, \\(\\Delta_k\\) is the graph of the skeleton of this triangulation. Next, the largeur d'arborescence \\(\\text{la}(G)\\) of a graph \\(G\\) is defined as the smallest natural number \\(k\\) such that \\(G\\) is a minor of the Cartesian product \\(K_k\\square T\\) of the complete graph \\(K_k\\) and some tree \\(T\\). In the paper of Colin de Verdi\u00e8re it is proved that \\(\\text{la}(\\Delta_k)\\) is equal to \\(k\\). NEWLINENEWLINENEWLINEIn the present note the author shows by simple and elegant constructions that \\(\\text{la}(\\Delta_k-e)<k\\) for each edge \\(e\\) of \\(\\Delta_k\\), which is then extended to show that \\(\\text{la}(H)<k\\) holds for each minor \\(H\\) of \\(\\Delta_k\\). This shows that \\(\\Delta_k\\) is a forbidden minor for the class of graphs \\(\\{G\\mid \\text{la}(G)<k\\}\\). NEWLINENEWLINENEWLINEIn the paper mentioned above, Colin de Verdi\u00e8re introduced a spectral graph invariant \\(v_1^K\\), where \\(K\\) can be taken to be either \\(R\\) or \\(C\\), and showed that \\(v_1^K(G)\\leq \\text{la}(G)\\) for any graph \\(G\\) and also that \\(v_1^K(\\Delta_k)=k\\). From here the author immediately obtains that \\(\\Delta_k\\) is also a forbidden minor for the class of graphs \\(\\{G\\mid v_1^K(G)<k\\}\\). NEWLINENEWLINENEWLINEAt the end, we mention that the author does not deal with the harder, but interesting question whether \\(\\Delta_k\\) is the only forbidden minor for the above-mentioned classes of graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939925$ADFE0BA2-0301-4718-87E4-39118E45386B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10aead0c1f296373702cd9c80b8bc98377857281","datavalue":{"value":{"entity-type":"item","numeric-id":3150174,"id":"Q3150174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b03f471bf67930ee8fefdfb9c81806e6f61b944","datavalue":{"value":{"amount":"+0.8239216208457947","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":"Q5939925$F74731EE-9B3B-4138-9AB9-75631562159F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6549ae90fe5f696cd4416c00e9a04883b84e568a","datavalue":{"value":{"entity-type":"item","numeric-id":5932703,"id":"Q5932703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31599d52d7c20f876d8f09ecda969d12b59fd3fe","datavalue":{"value":{"amount":"+0.7969707250595093","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":"Q5939925$079A757C-6A4C-4E12-9C56-23DD8E2F1BF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b709fb6d133337a1c91ba069f57ebd227e3df5c","datavalue":{"value":{"entity-type":"item","numeric-id":4838483,"id":"Q4838483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7de0a8b92db39f65d31fbcd26f4a31781b6527b9","datavalue":{"value":{"amount":"+0.7965174317359924","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":"Q5939925$9B2EF348-27CA-4BAC-966F-B0075662042F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2c1594da274eeababda0b6a1ed35d836416f6fc","datavalue":{"value":{"entity-type":"item","numeric-id":3475304,"id":"Q3475304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c4e286bcb31610278930f252d2e32a53ec82918","datavalue":{"value":{"amount":"+0.7615962624549866","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":"Q5939925$CA86F7A9-B448-47B9-ADEB-31EA254C058E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b6366bdbbde4aa1a26d9d3ebfe6692480301ec5","datavalue":{"value":{"entity-type":"item","numeric-id":705708,"id":"Q705708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2742389b00890800ccf912a2a6db90f6f51710e5","datavalue":{"value":{"amount":"+0.7464602589607239","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":"Q5939925$A652708A-75DA-4923-A125-E24D67DAA07A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5939925","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5939925"}}}}}