{"entities":{"Q2215468":{"pageid":2226211,"ns":120,"title":"Item:Q2215468","lastrevid":71573595,"modified":"2026-04-13T23:08:58Z","type":"item","id":"Q2215468","labels":{"en":{"language":"en","value":"Avoidable paths in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7284877"}},"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":"Q2215468$5EA429AF-C7D1-400D-8951-6E3B571CA69A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0db87b00bac2e0ad4060dcc4052701145662148a","datavalue":{"value":{"text":"Avoidable paths in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2215468$FE2AC8B0-7368-47F7-87ED-C323FBAA5606","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"844e3798e0e4b8592d242b6070d4585c8e6a0653","datavalue":{"value":"1454.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2215468$6F523DE3-8EC7-4615-B7B7-DDC4486E2BA2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"703d5124dbc0bf8c4a4d5e4b4ad36853f1372a45","datavalue":{"value":"10.37236/9030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2215468$FCC9008D-764A-4178-AD5A-0E9C774AE6CA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8eb893f819332112e861a74fd4234b6294c868f5","datavalue":{"value":{"entity-type":"item","numeric-id":306249,"id":"Q306249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2215468$E97E6A69-2884-41A8-A66C-3DDA46EF5216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc62afd685bf102abedbb40f59ef20f48a65705d","datavalue":{"value":{"entity-type":"item","numeric-id":2011656,"id":"Q2011656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2215468$C7B92EEA-EA4D-4D4D-A1EE-AAD9E57D784F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d6f4dfff2d62f9a663b528a4f63a4ebb98424b2","datavalue":{"value":{"entity-type":"item","numeric-id":1627177,"id":"Q1627177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2215468$8F7A37FA-D0FB-4FC3-A4BA-3E87576BD3EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"16ed018b25c80d88e663dccc2c16c7409b2c0440","datavalue":{"value":{"entity-type":"item","numeric-id":786036,"id":"Q786036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2215468$7EE39EB2-4624-4C61-96EC-26ACD3D73BF6","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":"Q2215468$05C80EB5-5472-4B8E-ACCC-19C63E10483D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6c22e955df7a052abb3ce5a1a5d7a826979ac81b","datavalue":{"value":{"time":"+2020-12-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2215468$E5603266-935F-4C99-9487-C979F377E1DF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"38b3fa60c6bd45661c33eedb775361333aae1eb2","datavalue":{"value":"https://arxiv.org/abs/1908.03788","type":"string"},"datatype":"url"},"type":"statement","id":"Q2215468$14135716-88DC-416C-A4BE-6CEEAC34007E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2040d81c02cf64a53deae7433432a75ade69119b","datavalue":{"value":"(The terminology follows the convention that an induced \\(\\dots\\) is an induced subgraph which is also a \\(\\dots\\).)  For a graph \\(G=(V,E)\\), a vertex \\(v\\in V\\) is avoidable if every induced path on three vertices with middle vertex \\(v\\) is contained in an induced cycle of \\(G\\). Let \\(P\\) be an induced path; an extension of \\(P\\) is an induced path obtained by extending \\(P\\) by one edge at both ends; the extension is failing if it is not contained in an induced cycle of \\(G\\); \\(P\\) is avoidable if it has no failing extension. Theorem 9 proves, for every \\(\\ell\\ge 0\\), that every graph that contains an induced path of length \\(\\ell\\) also contains an avoidable induced path of length \\(\\ell\\), which resolves Conjecture 1.1 of [\\textit{J. Beisegel} et al., Lect. Notes Comput. Sci. 11646, 126--139 (2019; Zbl 07152205)]; case \\(\\ell=0\\) was established in [\\textit{T. Ohtsuki} et al., J. Math. Anal. Appl. 54, 622--633 (1976; Zbl 0371.65006); in: 2nd supplement to the Proceedings of the 6th Hawaii international conference on system sciences. 1973, University of Hawaii, Honolulu, HI. North Hollywood, CA: Western Periodicals Company. 49--52 (1973; Zbl 0357.65024)] etc., and case \\(\\ell=1\\) in Theorem 6 of the cited paper of Beisegel et al. [loc. cit.]. The general conjecture was also motivated by results of \\textit{V. Chv\u00e1tal} et al. [Discrete Math. 256, No. 1--2, 445--448 (2002; Zbl 1011.05050)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2215468$5F930667-E18A-4093-AFD8-E0B7D67377AC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2215468$E35270B5-7C5B-4EF5-AE1C-B9582D46F4A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2215468$FE539FBE-4BB0-4A40-8755-F10B988D6FF2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"451444949331f47b7532efc1542c5957dde76c6f","datavalue":{"value":"7284877","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2215468$66964A8E-D835-4205-B51A-2CC7F2B70E75","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2344de0957bf4f83fdb916274429e77b4107eb11","datavalue":{"value":"avoidable","type":"string"},"datatype":"string"},"type":"statement","id":"Q2215468$C97B176C-8905-4FA3-BE29-F5C2C3351381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55564fc7b21f96f8b41d81d4b0602db635501a64","datavalue":{"value":"avoidable path","type":"string"},"datatype":"string"},"type":"statement","id":"Q2215468$D0327351-016B-4B45-967F-556C962AC9C1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2215468$B9507E3A-ADD4-4AB6-82F3-B37CF2AFDDED","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":"Q2215468$4ED6F9F3-A1CE-47B5-982B-C5DD1547B499","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4352a9bad31e1d1045e96db12d2746944ca58b34","datavalue":{"value":"W3113066384","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2215468$13883FDD-DACF-4ED2-BAD8-7354E0E13140","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1839dde592d4eebf103a334fb3d65cc26bf0724f","datavalue":{"value":{"entity-type":"item","numeric-id":2514166,"id":"Q2514166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2215468$92D6CCE8-0EDE-4DA3-BC70-6D3E7620BC7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"def53e8c8faf94adda459b9dcf91b45d69e567c2","datavalue":{"value":{"entity-type":"item","numeric-id":1392561,"id":"Q1392561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2215468$747EF162-EB44-4BDC-8E2D-68D127594E04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ea9071ba5b8778952f3a03ecc03417de2fceae6","datavalue":{"value":{"entity-type":"item","numeric-id":1849953,"id":"Q1849953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2215468$EDE25454-E885-4973-B784-523FE2084074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b43e3e48b388828a7b8aa17c3f81b7b754c93ecd","datavalue":{"value":{"entity-type":"item","numeric-id":773621,"id":"Q773621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2215468$FB810F85-4852-477A-A4C5-D1AA99898115","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"845ce1333fabf77b7b423f25aaa268be02121855","datavalue":{"value":"bafkreiay4vqhtfgwre7s5vme4c365gcuww7vbynre7so2r4hy26thvuzqa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2215468$2F142428-8F31-4AB4-924C-9E4CA84259F2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfb7236fb4b4961137e65b5c6c425a237fa3b547","datavalue":{"value":{"entity-type":"item","numeric-id":2285088,"id":"Q2285088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"430328d1846884c89d268b8dc40495d490c273f4","datavalue":{"value":{"amount":"+0.919847","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2215468$53307F69-292B-45EF-BC77-9A93575A5E36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8a9425cea5c0e03f2ed15792388a5dd7f45c17c","datavalue":{"value":{"entity-type":"item","numeric-id":1861577,"id":"Q1861577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7550ffd85ea42ea195e8a1aba7e2e655a499913","datavalue":{"value":{"amount":"+0.91841704","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2215468$FF4F4388-58A4-4287-88CB-CAC45120C0E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6facc6dcd95be773390592f9968875aaec6fafbc","datavalue":{"value":{"entity-type":"item","numeric-id":2107757,"id":"Q2107757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94d5973e25789154279e5f7febb462d39a01c608","datavalue":{"value":{"amount":"+0.8978152","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2215468$A6BF10C3-63C3-4A62-9141-BDBE1761F40C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f9eeadefc49322820728bde3c3c740e6e462659","datavalue":{"value":{"entity-type":"item","numeric-id":6108998,"id":"Q6108998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de48971e8db1919edc9f262144fbbff0329ccc37","datavalue":{"value":{"amount":"+0.89668536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2215468$365D35FB-247C-4B5D-85D9-CD1CECF5BFAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39e23a606be2613cea1053a3b82b3b5f7b789e43","datavalue":{"value":{"entity-type":"item","numeric-id":2260635,"id":"Q2260635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c9a381892b547c6006b6cd7efcc4a72097db908","datavalue":{"value":{"amount":"+0.89193046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2215468$D87224F1-26BF-4B00-99E8-7F5FF492EDBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67377d49fe670c378823b8f0f72cc6656e715349","datavalue":{"value":{"entity-type":"item","numeric-id":5127183,"id":"Q5127183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6eaa71a8a7bb15b7d650fd13f882e5c187c7041","datavalue":{"value":{"amount":"+0.8852005","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2215468$2ADCE94E-5971-449A-ACA7-BFF15CE179F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"822713333eaa515b4ffdd953df92c450fd195035","datavalue":{"value":{"entity-type":"item","numeric-id":878624,"id":"Q878624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0916a5e8485e4e60a6644fcb731b9e975f8f5203","datavalue":{"value":{"amount":"+0.8846638","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2215468$7D95DDE3-4C72-40C3-98EC-5F6C50C38164","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd9a450f0217d5e3b12ee14cdc658f85344bb89c","datavalue":{"value":{"entity-type":"item","numeric-id":3477977,"id":"Q3477977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56013d5059f1c5b129f1ca1916c91ddf4f161ec0","datavalue":{"value":{"amount":"+0.88280916","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2215468$6EB53591-E84E-4F28-9951-51812709FFCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"171b2f77e62cdc030428ae2c8db9f8234088be31","datavalue":{"value":{"entity-type":"item","numeric-id":4780288,"id":"Q4780288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4dd3aa9698f30bc81c13570ccbb0058bdb9a9dc","datavalue":{"value":{"amount":"+0.88208604","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2215468$51B98F26-A08A-4217-AD26-940182A85B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"052fe77cca345b73d4b2d58fcfe83691244a2e7d","datavalue":{"value":{"entity-type":"item","numeric-id":2065802,"id":"Q2065802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb06351b60d9694c19ff6234fbe09321491d44ee","datavalue":{"value":{"amount":"+0.88189715","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2215468$B94677B1-2D46-43C6-B6C1-52F196B223E5","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":"Q2215468$9E240E78-461D-4E60-8BE4-CEB94860E0C7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Avoidable paths in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Avoidable_paths_in_graphs"}}}}}