{"entities":{"Q5901518":{"pageid":8009265,"ns":120,"title":"Item:Q5901518","lastrevid":58616745,"modified":"2026-04-06T00:50:02Z","type":"item","id":"Q5901518","labels":{"en":{"language":"en","value":"Induced trees in triangle-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540946"}},"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":"Q5901518$601014FB-1EC4-4D50-8507-D798EE55C2ED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c57c6a06ab733a00b3150537be54e4656d3d1a23","datavalue":{"value":{"text":"Induced trees in triangle-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5901518$FD584EBD-B353-43BA-AFF2-C0709CA1DBEC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7466fa90f242b45d34d2aebeb8187fcebd5a15b1","datavalue":{"value":"1159.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5901518$15D4486D-9F24-4881-B4E3-88C980456518","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5205659b4c2831752a8f8604dc5b3ce7b9439fa","datavalue":{"value":{"entity-type":"item","numeric-id":818688,"id":"Q818688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5901518$08E2EF4E-7243-4971-844D-5993937962F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7affac58c4dbc5031cda82462f0e04c56bb86550","datavalue":{"value":{"entity-type":"item","numeric-id":190571,"id":"Q190571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5901518$C929489C-2244-4161-BEBF-3705C571EB24","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":"Q5901518$0403181B-B130-43EB-BA56-F4B8B8625156","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":"Q5901518$CFF2DFDB-90A8-4A70-A338-57ADF9F19907","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b40a773c8bc823c35c890cc12d8e3470e965d67","datavalue":{"value":"https://arxiv.org/abs/0711.4829","type":"string"},"datatype":"url"},"type":"statement","id":"Q5901518$2FD122CD-7C03-41C1-8127-AA0BD2A68DB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"e7039501b0d364bdc52445cd56df91bac57a38f5","datavalue":{"value":"https://eudml.org/doc/129766","type":"string"},"datatype":"url"},"type":"statement","id":"Q5901518$5E6D0261-1EB3-4BB7-AA62-EC9B6D4F9802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"f4d8541b05c180e73e3828e73598a1f6572a80aa","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r41.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q5901518$24BA50D2-E627-4A6E-9545-61B9C2F388D0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b6037a62a9fd8f555a48d3fdb0456dcb26be48a4","datavalue":{"value":"Summary: We prove that every connected triangle-free graph on \\(n\\) vertices contains an induced tree on \\(\\exp(c\\sqrt{\\log n}\\,)\\) vertices, where \\(c\\) is a positive constant. The best known upper bound is \\((2+o(1))\\sqrt n\\). This partially answers questions of \\textit{P. Erd\u0151s}, \\textit{M. Saks}, and \\textit{V.T. S\u00f3s} [J. Comb. Theory, Ser. B 41, 61--79 (1986; Zbl 0603.05023)] and of \\textit{A. Pultr} [private communication with the authors; see also \\textit{R.N. Ball} and \\textit{A. Pultr}, Cah. Topol. G\u00e9om. Diff\u00e9r. Cat\u00e9g. 45, No.\\,1, 2--22 (2004; Zbl 1062.06020)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q5901518$8BB46628-F77D-40FE-9ABB-20F3C2D9B0AD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5901518$6E01A849-432A-438A-82D2-5BEE9790698B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5901518$2038D6D3-E77A-4E23-BF81-CA180E18CF3B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1b2743ad82521b4a614fe282c6c594fcbd19770d","datavalue":{"value":"5540946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5901518$AEFA7324-67E6-43B6-ABEE-61D1582F81EC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85139424c50112b9b5a85fd369d8528dcee6cae6","datavalue":{"value":"connected triangle free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5901518$D7358678-9866-4EA5-AECC-85EDC1BE7D30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3e720d9896337f596fede65ab0c312a068e12c0","datavalue":{"value":"number of vertices of an induced tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5901518$23E9DDFD-67BD-413F-A99B-4CA82EB8DB06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q5901518$FBE28F8B-1F9E-44EF-954B-2B844BFB6F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b1beb3ef8c683e5be5d037c048db04fe9020394","datavalue":{"value":"blow-up construction","type":"string"},"datatype":"string"},"type":"statement","id":"Q5901518$105BAA6E-20B3-480D-9169-9D66E57B091F","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":"Q5901518$1568C194-76FD-46EF-8B44-F35924507005","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"415232af5e5a6eb34b90fbef97530b32abdc05af","datavalue":{"value":"bafkreicaez7rm65qj4grhjdsy4cmwxxkyetydt7hygbwpmxpjoyxqvs3xe","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5901518$62923F14-C1D3-4D43-A47A-5BA647037EE0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a69e1bafddde7f414d59d52f85c56a1eff3625e","datavalue":{"value":{"entity-type":"item","numeric-id":5900077,"id":"Q5900077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1c3c922c78204a488a90d3d4079804c297c31eb","datavalue":{"value":{"amount":"+0.9925552010536194","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":"Q5901518$90EF5B24-1A6A-4C73-9ACD-4AD6800AF3BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61b3f876bf7df9048325a84bc7564c6d4fac1e14","datavalue":{"value":{"entity-type":"item","numeric-id":1003853,"id":"Q1003853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0694e290c2a025bdc88f91dd22d62888e5c3d5a0","datavalue":{"value":{"amount":"+0.9151021242141724","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":"Q5901518$9BDFA06F-25DA-45A7-803D-16AFF7C4CD9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24cc1aee0ff49da1122496f561c61e126eb92664","datavalue":{"value":{"entity-type":"item","numeric-id":3055916,"id":"Q3055916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7147e1990b5bd589627b000245cce445f6f8bb9","datavalue":{"value":{"amount":"+0.8894215822219849","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":"Q5901518$3B7AC804-D7A4-49CE-95D3-962A880193F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fe6deecdeb18d62a8b6e6734363fd67ed02ee98","datavalue":{"value":{"entity-type":"item","numeric-id":1082351,"id":"Q1082351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"132e109e1e54139532f09871a232d0a38ab19842","datavalue":{"value":{"amount":"+0.8204731941223145","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":"Q5901518$2423627F-B0A5-47F0-B0FA-775E14AB6EF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfe2e2d9da49e5db42d7ee2a8ae72742cd5786e1","datavalue":{"value":{"entity-type":"item","numeric-id":3575471,"id":"Q3575471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"063c9fd52a2b9cf2ef402492380283964b8dd082","datavalue":{"value":{"amount":"+0.8173737525939941","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":"Q5901518$F0AE7E7F-CDB3-4058-8CA8-7F185FD0D59E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5901518","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5901518"}}}}}