{"entities":{"Q844235":{"pageid":846083,"ns":120,"title":"Item:Q844235","lastrevid":64766748,"modified":"2026-04-11T22:05:05Z","type":"item","id":"Q844235","labels":{"en":{"language":"en","value":"The four-in-a-tree problem in triangle-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5659956"}},"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":"Q844235$1BA3814A-4181-462B-B5B0-6890F199B713","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5cd4694379f295f92206045a07f47c2be581678a","datavalue":{"value":{"text":"The four-in-a-tree problem in triangle-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q844235$00C76159-3938-4230-8EAC-313391EE5DF9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"49086c6afa239ef131ee5e43a5ba9387abd58632","datavalue":{"value":"1186.05101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844235$0E987D3B-B0A5-4C94-A6EA-8354EA1BC0CB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b7ace27bc9a88c5772098f9c9c5554bd9ff97ca7","datavalue":{"value":{"entity-type":"item","numeric-id":844234,"id":"Q844234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844235$048C1F6F-556E-4357-A11E-28462094C347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8dc252585538d2ef4e07162cef61c79e437a3117","datavalue":{"value":{"entity-type":"item","numeric-id":411243,"id":"Q411243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844235$9B642FB2-1DF6-48E4-A341-EB1C0B279826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba8963bf07877ded4133836acba07ecf77a509c7","datavalue":{"value":{"entity-type":"item","numeric-id":442236,"id":"Q442236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844235$16C3F520-09E7-4D18-A6FA-DB44CD706905","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844235$A52A3C6C-3AC2-4CAB-8CBC-2817DC8E2C90","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"160ae7be62905e153a649a9a4d09ab3aa02ded62","datavalue":{"value":{"time":"+2010-01-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q844235$9D8744FF-F47C-4A7A-B3D1-A1EA49D80AC2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4346921ad408d73957fc0a5c0b437c5e751eec09","datavalue":{"value":"https://arxiv.org/abs/1309.0978","type":"string"},"datatype":"url"},"type":"statement","id":"Q844235$6CA66BD7-2C04-4176-A443-C8F0A2D07D13","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"05ee5d84d8e34769b14627556fc779367cd22c2a","datavalue":{"value":"The three-in-a-tree algorithm of \\textit{M. Chudnovsky} and \\textit{P. Seymour} [``The tree-in-a-tree problem'', Combinatorica (to appear)] decides in time \\(O(n ^{4})\\) whether three given vertices of a graph belong to an induced tree. Here, four-in-a-tree for triangle-free graphs are studied. The paper answers the question: what does a triangle-free graph look like if no induced tree covers four given vertices? Main Theorem: Let \\(G\\) be a connected graph with 4 distinct terminals. Then either (1) \\(G\\) is a cubic or square structure w. r. t. the four terminals, that is \\(G\\) is a cube or a square with 4 pending vertices, or (2) \\(G\\) contains an induced tree that covers the four terminals.  The authors provide an \\(O(nm)\\)-time algorithm that given a triangle-free graph \\(G\\) together with four vertices outputs either an induced tree that contains them or a partition of \\(V(G)\\) certifying that no such tree exists. They prove that the problem of deciding whether there exists a tree \\(T\\) covering the four vertices such that at most one vertex of \\(T\\) has degree at least 3 is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q844235$FA62A0A2-BA94-4424-8C46-AA5A15B954AA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844235$E1EA42CA-C0A8-42B4-9626-D5F9CE572FEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844235$34FC6487-11EE-4E20-A6D5-3E0D3E410A44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844235$446BC5D3-4039-426F-BE22-68AA7B62277E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844235$DB5A2D6D-F87D-4116-8BED-8265FD8329B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844235$53DB10B1-A1E1-4A43-854E-C879706373E2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3620a08d0591d62aae6a960c1c2505bfe9c09701","datavalue":{"value":"5659956","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844235$CAA9FEAB-BAC7-4232-AEFD-1398CCC8CAB6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6be65e93211f56d0c1caf92dc6edaee001a8d73","datavalue":{"value":"three-in-a-tree algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q844235$6D0B87A7-277A-4649-833A-FC6854DF2DEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ce67bd27fc3ee89d8642921735100b79f0d0ab3","datavalue":{"value":"triangle-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q844235$D8B3A091-CB1B-4A29-A6E7-996DDD26B7FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63c1434323ab49931c3af95549372679e5687894","datavalue":{"value":"induced tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q844235$65E7A989-586E-4B79-AD88-384D5D9B5F3B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"85e4af3c816f7ac40605750dbfec22d9e5ba7cdc","datavalue":{"value":{"entity-type":"item","numeric-id":207731,"id":"Q207731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844235$B1858B1D-FFFB-4B9B-A94F-246815D9F229","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":"Q844235$0510E253-FE26-44EC-992D-DC07C41C71EC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b3d6b27056ee9d417a0f3cb68e5d705be84742e1","datavalue":{"value":"W3099919903","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844235$88006CF4-7D79-4FF2-85C2-35B39956FA2B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82cfa9f684c3350648874deb95288407da9381e","datavalue":{"value":{"entity-type":"item","numeric-id":1175980,"id":"Q1175980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844235$41517E81-D8AA-4685-9F41-360E1C0D845B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fcde29f530320a1564e0133ddd6355912d9efcc","datavalue":{"value":{"entity-type":"item","numeric-id":5421811,"id":"Q5421811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844235$1260A8DD-C29E-4438-948E-65AC575165FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b829a142a09b5703fa75e4c561943be530af1676","datavalue":{"value":{"entity-type":"item","numeric-id":653792,"id":"Q653792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844235$0A7AE74C-596B-4353-8A49-2E1457684D04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0262c7ca9d46cfb4cf3512f2a0333529706ee62","datavalue":{"value":{"entity-type":"item","numeric-id":3684121,"id":"Q3684121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844235$21FF9D6C-395E-4529-9D87-3EA0E85DF852","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"681890a22185a556c79810baae0257408fedb350","datavalue":{"value":"10.1007/S00373-009-0867-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844235$3A84DCC4-B47F-42F5-8A65-C9B08BCB2B13","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fd0438ca2d96e016cf21341d628568c7b075984","datavalue":{"value":{"entity-type":"item","numeric-id":602681,"id":"Q602681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54ec35a62efa22f2a23078f0c2aa8c1ebd91c4d1","datavalue":{"value":{"amount":"+0.8268156051635742","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":"Q844235$CC0894D7-F717-4772-8DA9-A32A121D5F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a94ec730e8eb4c5e9e849ea9a3199001f28d45d","datavalue":{"value":{"entity-type":"item","numeric-id":653792,"id":"Q653792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8fbfa73bad0fafaae65bce4049f59f91a4c947d","datavalue":{"value":{"amount":"+0.80926913022995","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":"Q844235$7E3824B9-1820-452C-BDE5-B673E6217219","rank":"normal"},{"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":"dd3c354d244268664313fb68e58f7bd7339cfa1b","datavalue":{"value":{"amount":"+0.7794601917266846","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":"Q844235$B9A764BC-FD98-4456-BB6B-25CE56DEB9D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7eff3d9422a8f183594c41ed679785905da6b6a3","datavalue":{"value":{"entity-type":"item","numeric-id":5901518,"id":"Q5901518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b8c8f8040f5e677c8d85d4c7a0e300b19dc2372","datavalue":{"value":{"amount":"+0.7781944274902344","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":"Q844235$CF37D6CD-EC35-4E72-9E36-6CF6F8FFD413","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":"3994271a57d4bd67830249969d8177f280f32174","datavalue":{"value":{"amount":"+0.749544084072113","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":"Q844235$F4BBF64C-270D-417C-AD8F-E1F3EF66DAF7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The four-in-a-tree problem in triangle-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_four-in-a-tree_problem_in_triangle-free_graphs"}}}}}