{"entities":{"Q707020":{"pageid":708869,"ns":120,"title":"Item:Q707020","lastrevid":63682653,"modified":"2026-04-11T14:49:55Z","type":"item","id":"Q707020","labels":{"en":{"language":"en","value":"Girth and treewidth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2132705"}},"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":"Q707020$23DB4602-A815-4D06-AD49-404DA537DAC0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"109188e43e5d2fe8d1bd95d77e26b36ec635898b","datavalue":{"value":{"text":"Girth and treewidth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q707020$2B559AE1-A099-4E42-B3C3-D5D833B1494D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cfcd217e259489537828aa2cf66b6d442ff93658","datavalue":{"value":"1064.05084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q707020$6F809C45-FD5F-4F27-890E-F421A7F00A99","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":"Q707020$FA252248-984E-4EB7-98B3-BA7FE26618E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"119fbbf23967ffad7b319a3cca84803ae6be69b0","datavalue":{"value":{"entity-type":"item","numeric-id":536213,"id":"Q536213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$294CC9A6-728E-4D77-893E-882E87E438D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$92552FC2-89E3-46F0-9EE5-244710BD185B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0bb430d98445fad0c07a301b258c507df3dbc1f9","datavalue":{"value":{"time":"+2005-02-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q707020$D2433772-2C3F-4E83-8713-79B3B136533D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"57e7be9fa2f4b0008a81be7811ec77f29b769b66","datavalue":{"value":"Graphs of high girth have been much studied, especially in the context of the minimum vertex number of graphs of given girth and minimum degree. The authors study the treewidth \\(\\text{tw}(G)\\) of a graph \\(G\\), giving a lower bound in terms of the girth \\(g(G)\\) and average degree \\(d(G)\\). They show that  \\[ \\text{tw}(G)\\geq c {1\\over g(G)+1} (d(G)-1)^{\\lfloor (g(G) -1)/2\\rfloor} \\]  holds. Since the treewidth is smaller than the vertex number of the graph, \\(\\text{tw}(G) < v(G)\\), and the existence of a graph with  \\[ v(G)\\leq c^{\\prime} (d(G)-1)^{\\lfloor( g(G)-1 )/2\\rfloor} \\]  is conjectured, this bound appears to be almost tight.","type":"string"},"datatype":"string"},"type":"statement","id":"Q707020$84C18F07-7EE0-492B-BC8B-D4053B71CF34","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q707020$241733B9-19F1-45E4-B523-EE695781B488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q707020$A5ED4B60-BBFB-40E3-9FE7-33CCF143578B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q707020$24D02650-6287-4832-A9B9-89668B8E1982","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4184537e899d81c4aa07b13ad527ef8634b1c264","datavalue":{"value":"2132705","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q707020$B7E9347A-ECBC-4A5A-BDC9-7048AB397385","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b10cff0c23b9f6aa8789d5f16a4c9af5f5c9cb04","datavalue":{"value":"average degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q707020$EFABBBE8-51EF-4A31-BB33-C511D4B631AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f1e625afea5b1a633df9fe58ad43c2d03e075ec","datavalue":{"value":"tree decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q707020$31F77E23-2C26-47CF-8AB1-5ACCB34B61C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"766ab1e2874ed03ff460fb8b3c0c52f9f57ea578","datavalue":{"value":"minors","type":"string"},"datatype":"string"},"type":"statement","id":"Q707020$DCDA05F7-FB22-4CD5-82FB-1878733DFD86","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"13b2797137908bf085ac37482e4ca3bd3f2ade57","datavalue":{"value":{"entity-type":"item","numeric-id":587716,"id":"Q587716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$380066F5-1C8A-4C22-A676-8BFF6D02B40A","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":"Q707020$67BFECC1-43E3-4287-BF5C-56F6FBBFBA66","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4d06b01121e038cac721c39552b25317aefb9f77","datavalue":{"value":"https://doi.org/10.1016/j.jctb.2004.05.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q707020$29F92F54-00B1-40C3-A437-191280712935","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"02728723a8e58edcf7d6a66480a0eac77a79a1a2","datavalue":{"value":"W2081464744","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q707020$56A4373F-A808-4C9F-A64E-61F085B2A198","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e0da50e9870f8cb226026bbc1ec21e379f11349","datavalue":{"value":{"entity-type":"item","numeric-id":1348665,"id":"Q1348665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$E30BAC59-D76A-4C48-88AE-AC025C13FDD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"924e802243b4f51c1822e67211b88d08172a8079","datavalue":{"value":{"entity-type":"item","numeric-id":1062758,"id":"Q1062758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$1D607EED-1575-4DC9-B2C1-A942C77061F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f96a660eaa4e8b33419c867ffedb789edb466ebc","datavalue":{"value":{"entity-type":"item","numeric-id":1116705,"id":"Q1116705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$A00E620F-3BDE-4527-A33D-9157DEF69159","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93084df5751505b3c6a721eac731896a3039b3fc","datavalue":{"value":{"entity-type":"item","numeric-id":4291429,"id":"Q4291429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$1D8EC741-CA7B-461F-AAF6-8B99E97A13C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747a911f10480a7188a201d8808620458b2a3690","datavalue":{"value":{"entity-type":"item","numeric-id":5691297,"id":"Q5691297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$59556D9C-6939-4584-BD62-935199659A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae867168c941791a545c80d9051c23a76351caec","datavalue":{"value":{"entity-type":"item","numeric-id":4210129,"id":"Q4210129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$1155ACA9-8BD8-42FD-9B17-82D63B325DB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$5EABCF73-E826-44DA-A1E2-DA0E51B83786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31e0fecf37e8bbc869084699ebc361b1e96d6394","datavalue":{"value":{"entity-type":"item","numeric-id":4871748,"id":"Q4871748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$24D801C5-A10B-47C3-8B88-EBBA641A2AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00ed32a7cb7e7da39f6bee5d93d58cf00d5f1608","datavalue":{"value":{"entity-type":"item","numeric-id":4551369,"id":"Q4551369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$FF07E574-D63C-4C5B-BB05-032291FAA167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52d6eb6b62c08cc23c2e862a5b494ee68c1ad962","datavalue":{"value":{"entity-type":"item","numeric-id":4443093,"id":"Q4443093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$979F722A-6E20-4C80-BD7A-BE3F14980B1E","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":"Q707020$E26E8EBE-DEEE-4E61-88D6-42D79114913B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49ae909d48dac5fa6b84f6156f1fb024f6dbfc27","datavalue":{"value":{"entity-type":"item","numeric-id":558318,"id":"Q558318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$E41504C6-5EDC-4801-A3D3-F90A55DB2A67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$68A87CCE-AD32-488A-B417-B86956681E8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c59623c60a6e1386539c0ef28bfc016f6933ca84","datavalue":{"value":{"entity-type":"item","numeric-id":760439,"id":"Q760439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$EA1353E3-87A6-433B-835D-84622F0191F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc9d0fb35664d596a28ec73c5cf6274eaa1b799b","datavalue":{"value":{"entity-type":"item","numeric-id":4800396,"id":"Q4800396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$220E4A9A-B867-4E67-B04E-3BEFD630A4F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3f692ed51a7a041e993c6dca99b9c971ba8cbad","datavalue":{"value":{"entity-type":"item","numeric-id":1403927,"id":"Q1403927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$49DCB2CA-253E-4156-9C7D-EAE51CA126C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9b412d3a3f8a72fa05cf170399c14d70d282e3b","datavalue":{"value":{"entity-type":"item","numeric-id":4819248,"id":"Q4819248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$EF583F5F-E862-404C-B973-7BE706518C55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7c5471047c68ce2128bcd2e4825a83d05c00761","datavalue":{"value":{"entity-type":"item","numeric-id":1307355,"id":"Q1307355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$B839A6B7-CB32-4C06-8766-E3CAFFF03181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6760c1a0ed84f473ebf9c19dbb4d05bbf42b9a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3751592,"id":"Q3751592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$1773FB9B-C130-4611-A082-D0BC27CAE871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d2866bc4bcd7c7ce818a84a1b498b2836e7672e","datavalue":{"value":{"entity-type":"item","numeric-id":792338,"id":"Q792338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$25743CC7-B278-44E2-AFA5-9B09AF3B0A28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b76156a4d5397786b7acde2677b3463186b48aa6","datavalue":{"value":{"entity-type":"item","numeric-id":3344229,"id":"Q3344229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q707020$0EB9AC35-AC78-4BAC-A77B-2BDDA20DDBA6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ede2f670c55c797ca2d20053c6f7920f3b2e7273","datavalue":{"value":"10.1016/J.JCTB.2004.05.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q707020$7934C903-CFEE-4029-ABF7-241B6E176511","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ffb28437b0595adc5535e38ccb31dfdf738cc311","datavalue":{"value":"Q131848296","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q707020$306D200A-AB3E-4591-81D8-EA43FD5CC2A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96cc5f85139fd08c30e88105efa6aa58ed40e0c5","datavalue":{"value":{"entity-type":"item","numeric-id":1850563,"id":"Q1850563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28a42e8c0e81c4b9eb19c2af847dd409dc1547d8","datavalue":{"value":{"amount":"+0.7651032209396362","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":"Q707020$AC7FDBCD-102C-4A0E-88C8-80515E738286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2a952b7041a05eb12996ce92d5c59d26feec460","datavalue":{"value":{"entity-type":"item","numeric-id":6081551,"id":"Q6081551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf00f7628c569f3c7887295ee73419ef12a1dd68","datavalue":{"value":{"amount":"+0.7581974267959595","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":"Q707020$D7FBD6C6-D9BB-48DA-B22E-3D90E3906235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce7aaec4e1a7802235a8a2db001a92e8f65afc44","datavalue":{"value":{"entity-type":"item","numeric-id":558318,"id":"Q558318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9324967c08106bcc01eea82d5b2a178875e0c431","datavalue":{"value":{"amount":"+0.7571556568145752","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":"Q707020$A82FE6BE-E45F-4917-8B4A-1659067A0D9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bd336cd3d0a712c3f2f4eaaa7fe827731e58e43","datavalue":{"value":{"entity-type":"item","numeric-id":2400974,"id":"Q2400974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fc6d0605fc181be3c2be80be7fb0400a6165caa","datavalue":{"value":{"amount":"+0.7537260055541992","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":"Q707020$BBA61937-BF0D-4C35-887D-A104C5F7B452","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0760d072e25715b88ea472b96bae092a1b64c3b","datavalue":{"value":{"entity-type":"item","numeric-id":3651179,"id":"Q3651179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05e04fd77dadfbc8f707b2ddf1a1d9c5c4a81d5a","datavalue":{"value":{"amount":"+0.7528932094573975","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":"Q707020$2B104277-DEF4-44BC-8B3B-2B639D9E99A9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Girth and treewidth","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Girth_and_treewidth"}}}}}