{"entities":{"Q2684889":{"pageid":2695632,"ns":120,"title":"Item:Q2684889","lastrevid":56684739,"modified":"2026-03-18T19:36:42Z","type":"item","id":"Q2684889","labels":{"en":{"language":"en","value":"Long induced paths in minor-closed graph classes and beyond"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7655013"}},"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":"Q2684889$B0CD16A6-94CD-4BD3-8619-FB05E5AF1383","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc214aed96512248678f509ad04c73f95a5b73e0","datavalue":{"value":{"text":"Long induced paths in minor-closed graph classes and beyond","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2684889$84A1519A-B64E-40DB-8483-3722E7172CAB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"08f53b64b7fd4598f26083c67860d034aac75f53","datavalue":{"value":"10.37236/11029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684889$44A96F7D-8C8A-4418-B10B-784ADF7249F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"69431465bc81a145e8d63b4fe1d15f8e0016e30e","datavalue":{"value":{"entity-type":"item","numeric-id":2684888,"id":"Q2684888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$27656AD6-8353-48BF-9F9D-2E65F5E079E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"001bf7e8cd12734854d271c49ff106c597b12f4e","datavalue":{"value":{"entity-type":"item","numeric-id":284714,"id":"Q284714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$9F231E72-4E9B-4564-9365-4230CE7AF130","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":"Q2684889$ABDF4D32-086C-43A2-A826-ECB4589A24ED","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2c66fb7aab39afe15eb7d8af0079ba7f34f4d9d","datavalue":{"value":{"time":"+2023-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2684889$109E7B41-9022-4ED8-B411-54F7D79E702F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e9eefb70888b9e10065271d5bd87da44d0aafc2a","datavalue":{"value":"https://arxiv.org/abs/2201.03880","type":"string"},"datatype":"url"},"type":"statement","id":"Q2684889$1E04E071-646C-4E78-BF69-CE2471056363","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f3f6d69d9a26bcb5ff61a148c231699cc74d9ccf","datavalue":{"value":"Summary: In this paper we show that every graph of pathwidth less than \\(k\\) that has a path of order \\(n\\) also has an induced path of order at least \\(\\frac{1}{3} n^{1/k}\\). This is an exponential improvement and a generalization of the polylogarithmic bounds obtained by \\textit{L. Esperet} et al. [Eur. J. Comb. 62, 1--14 (2017; Zbl 1358.05148)] for interval graphs of bounded clique number. We complement this result with an upper-bound.  This result is then used to prove the two following generalizations:  \\begin{itemize} \\item every graph of treewidth less than \\(k\\) that has a path of order \\(n\\) contains an induced path of order at least \\(\\frac{1}{4} (\\log n)^{1/k}\\); \\item for every non-trivial graph class that is closed under topological minors there is a constant \\(d \\in (0,1)\\) such that every graph from this class that has a path of order \\(n\\) contains an induced path of order at least \\((\\log n)^d\\). \\end{itemize}  We also describe consequences of these results beyond graph classes that are closed under topological minors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2684889$3F0572F7-1B1F-4FAD-85FB-9E52FBC73866","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684889$75D96137-CE35-43E9-BB97-3224F98B39A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"26ba4f06ff5c7e92bd3a85f32aa625ae214ffe0f","datavalue":{"value":"05C31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684889$09DCF155-38A5-48E0-AF6E-872813C08349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684889$43855FD5-5237-449F-8E4C-0BCFDDEA2C66","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"092afc948e55b6de42ca67d526fde0a6c7b2a3b7","datavalue":{"value":"7655013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684889$469DA7D0-CAD8-4237-A5A1-11D0A71EE1E9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29f4571ade1a0163108052b73cb5e3ac089feed4","datavalue":{"value":"maximum lengths of paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q2684889$731ADBFE-1E3D-433A-9B6D-6BC4DC173C6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15de7c8f26b1b5a6fcdee5057649f3ce6bc4292c","datavalue":{"value":"induced paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q2684889$562598C3-5A1A-4AA3-8D76-6719A2ECCF3F","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":"Q2684889$DE85D6EC-6399-41E5-9C75-E55844144A01","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bf660da966410aa6f0b25703ef1a2739409f2f71","datavalue":{"value":"W4310381270","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684889$26B38EDD-08F0-476A-98F0-654172D63505","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e814563a25069dac14b096820b19107909334cec","datavalue":{"value":{"entity-type":"item","numeric-id":1713790,"id":"Q1713790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$507E0667-E9FE-49C4-BF5E-7EC4ECB5150B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0508063bbc6485c8f0cbdc4c198a6b9ff8c0e092","datavalue":{"value":{"entity-type":"item","numeric-id":4522464,"id":"Q4522464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$8E80A243-327B-487C-9017-4C186F83F4E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"211530a7d66720062b60e82cf130f31beea4a662","datavalue":{"value":{"entity-type":"item","numeric-id":1975365,"id":"Q1975365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$A3A430B9-1742-4C65-9D7D-9B330211CBCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec11463fe2d60a303760ce9865ecede41d671bcb","datavalue":{"value":{"entity-type":"item","numeric-id":1850624,"id":"Q1850624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$79E0A233-8AEC-465D-82AE-5D2E430D3F3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26fe1e94c3aa29ec54309da8dc13d21361b3acc6","datavalue":{"value":{"entity-type":"item","numeric-id":290522,"id":"Q290522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$DDD51952-8005-4572-A805-B08D1697EEA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d675f62019ad4b450cbe016ccd3a4e323388dc2b","datavalue":{"value":{"entity-type":"item","numeric-id":2407382,"id":"Q2407382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$A1C4D28B-9D9F-400E-BAEA-2A58047035EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63a14f0801782af4369063d3763cb14039308a46","datavalue":{"value":{"entity-type":"item","numeric-id":518170,"id":"Q518170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$3F055C3D-914C-49CF-8B71-C4F3BC20977C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e458531dc8f9b4a4f76ca8cb6a5d9d31ac768ee2","datavalue":{"value":{"entity-type":"item","numeric-id":2562090,"id":"Q2562090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$F47F8544-86AA-4D47-A497-C2C9930C7B9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f346f6935eab8f7bfd8c5b35d3ff010b785bc3a1","datavalue":{"value":{"entity-type":"item","numeric-id":4860774,"id":"Q4860774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$820F1B11-CB8D-4AB1-AB87-8B0EB0DFAB38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11fe7f6a71424bcbca2227e0757bb4b3f123994f","datavalue":{"value":{"entity-type":"item","numeric-id":5252660,"id":"Q5252660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$779C7308-E647-403E-8DD5-90C94DDB38C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6de6f36eb025a6c05ae4c9d474774c3991c46cb2","datavalue":{"value":{"entity-type":"item","numeric-id":1160143,"id":"Q1160143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$76BD3EF6-3663-485B-8440-0B534B229314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a8c44dbfa488b5bd1e374fbb8b00fe1343e1c82","datavalue":{"value":{"entity-type":"item","numeric-id":2766682,"id":"Q2766682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$35FA7427-130B-4443-AD57-F64FB8555306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1126028165ed25aec0b23ea9dd66a35457a4e03a","datavalue":{"value":{"entity-type":"item","numeric-id":419416,"id":"Q419416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$5AB910C4-0312-4C55-830C-769B52223515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43805ffe067a9a027d8ff41bfb7dac05c170dd0f","datavalue":{"value":{"entity-type":"item","numeric-id":3836524,"id":"Q3836524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$4070E190-B409-4834-B9DC-DD54D684B1A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb0a3e3e66ee3b16a19ca5733c4fa285fce7570a","datavalue":{"value":{"entity-type":"item","numeric-id":1410731,"id":"Q1410731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684889$0D9438EA-BAF2-4D4B-9DE1-EC843DB6E7D6","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ac7a8c2940a07e721c98ce72bc4f1f29ff5688ca","datavalue":{"value":"bafkreigvr66bvwkxgk6jpiwjqdlcj4hviavkzm5vyznmrkqksogpbtllai","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684889$27780FAC-066F-4678-BF0E-41EA4BA0FEBF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"924f97b5097310ce756214b173cefb6e41309464","datavalue":{"value":{"entity-type":"item","numeric-id":518170,"id":"Q518170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4a157d0996d47999835f946e3bdbaac06d2daa7","datavalue":{"value":{"amount":"+0.8290677666664124","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":"Q2684889$0CB91F60-EA1C-4CE2-8CCD-1CBCCD8A572E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0be823ca47c06ada325bcfcb93ad219d5ad9e6f9","datavalue":{"value":{"entity-type":"item","numeric-id":1907107,"id":"Q1907107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce1e83d40ca90f05cea38da96e32bc9b53e1342a","datavalue":{"value":{"amount":"+0.7794098854064941","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":"Q2684889$55AAB5CD-BB24-46DA-8514-915433698A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"220fdd6d5738740f94b148d99376d55be3ef3f30","datavalue":{"value":{"entity-type":"item","numeric-id":6162145,"id":"Q6162145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cc8ee04cb0a385e01bdd0cf41033b4156898042","datavalue":{"value":{"amount":"+0.7725841403007507","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":"Q2684889$B18A60E9-5985-451B-ACD0-082FBA288322","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cd2d92b4673b241cd767e56027462c0d46eba1d","datavalue":{"value":{"entity-type":"item","numeric-id":5130575,"id":"Q5130575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d060de32ca38104c9607c70d3f963c9ddcb17b8b","datavalue":{"value":{"amount":"+0.7725424766540527","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":"Q2684889$083637FE-158D-4B1F-88CE-555C2D49D347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"badf4ff8ac8a1a6d3e13cc8aecce2e5e84a6db70","datavalue":{"value":{"entity-type":"item","numeric-id":290522,"id":"Q290522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78595b4f706cd172850d3c894530d9631f397588","datavalue":{"value":{"amount":"+0.7703919410705566","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":"Q2684889$21777096-464A-4876-96F4-65C2622754D8","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":"Q2684889$D88B9F32-13F3-485E-9F64-FD46D4442251","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2684889","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2684889"}}}}}