{"entities":{"Q2781059":{"pageid":2791797,"ns":120,"title":"Item:Q2781059","lastrevid":47761114,"modified":"2026-01-02T15:15:17Z","type":"item","id":"Q2781059","labels":{"en":{"language":"en","value":"Large induced forests in sparse graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1720261"}},"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":"Q2781059$2EB4B840-9DDF-4AB0-B5FB-A9611D0A17E2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"35cf5ee1698008f7f60c1320a3942c4a46206cbc","datavalue":{"value":{"text":"Large induced forests in sparse graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2781059$89B8FA06-158B-438E-B802-4384B3F1CE5B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bd1854265c170b37521e64cadfbc6daa79073152","datavalue":{"value":"0986.05060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2781059$0C9EADD1-A9A3-42AC-8313-E99F9B20AC1B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2781059$BA93E85E-72A1-4C72-A18B-4BF3DEFBEAB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b2dc7fb86714f67c87c73e07c13ee1e0d7b9d71","datavalue":{"value":{"entity-type":"item","numeric-id":168649,"id":"Q168649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2781059$03048CDF-67CE-4721-9996-858B85924013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c767c73643f6f9c229d2e29427c218355d7fa9cd","datavalue":{"value":{"entity-type":"item","numeric-id":186136,"id":"Q186136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2781059$3B2BEAFE-7A39-4FAF-A042-EE9D318E5DAC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4de5c7a5d238217ab4a071d198b3a40ee05be465","datavalue":{"value":{"entity-type":"item","numeric-id":2725046,"id":"Q2725046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2781059$830EAAF7-B97C-4858-8DB0-FCCA40F41A40","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"89979698039692d8b30dd476805176a82a96347c","datavalue":{"value":{"time":"+2002-06-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2781059$821FC43D-7415-48B5-B10A-EF4CD6B3A95E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2781059$AB5825D4-6CA6-4D68-931F-6191496E1AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2781059$935E438A-824C-4B3B-9429-8E3BD513B94E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2781059$1025DEE9-E913-487E-ACDA-C3CC97B15506","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bfb7abea200689362e8bfea4ddba89d53c7bb074","datavalue":{"value":"1720261","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2781059$8A4188FE-BF27-4BB4-BFEB-28E4CFB38424","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc79eafc1d9ceb1ab79797a36449e9df369395df","datavalue":{"value":"forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q2781059$13B404CC-0DBB-455A-AC7C-7957F7C8D474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fcac84b24323d606be1f1f5291be554d1d8ef917","datavalue":{"value":"acyclic set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2781059$7C8E9335-2189-448A-87E9-C911BD35D979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2781059$0F8DA999-D862-4A71-9E10-AA106C1F8710","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":"Q2781059$2C0ABF4C-C264-408D-A168-AB563EF87A55","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0046a277d87a3c7e57ee3ac1ba28d820b03781d9","datavalue":{"value":"https://doi.org/10.1002/jgt.1028","type":"string"},"datatype":"url"},"type":"statement","id":"Q2781059$A0178FBC-D05A-4602-828D-BBC762A9A25C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2225a208182d1a483c29c9d5fb38261147fb89b4","datavalue":{"value":"W4242102268","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2781059$8AAEF27D-F7DF-4F3C-92C4-8FD917170979","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52c7540760fe9ef3923a27be3c87c2aba62dfedc","datavalue":{"value":{"entity-type":"item","numeric-id":1149967,"id":"Q1149967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2781059$59F8F4D8-BBC1-4839-A625-0ECF8AED6677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e24c1f3abeac7a85848c686b9ccd0c7e0b58d1eb","datavalue":{"value":{"entity-type":"item","numeric-id":1092059,"id":"Q1092059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2781059$D4A7867A-9A5B-4201-B069-179DF3EDEFA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbac5c562486055a547edb14947d8120c5dc2132","datavalue":{"value":{"entity-type":"item","numeric-id":1252865,"id":"Q1252865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2781059$ABC037B5-4DA9-497E-B146-6CE64313ED6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fad64547aa8c484ae73fda6b3bc2f85436a1625d","datavalue":{"value":{"entity-type":"item","numeric-id":1052343,"id":"Q1052343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2781059$DC6BEC15-6903-4DD7-93DF-99C5578F1E06","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6187fb191010ecea4a7c98412957f5e39337de44","datavalue":{"value":"10.1002/JGT.1028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2781059$C34EB0E0-FFC1-4425-9A74-B82729CF50C3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0cbeca683c8345039edd6a77d85ae87c927f37fa","datavalue":{"value":"A set \\(S\\) of vertices of a (simple, undirected) graph \\(G\\) is acyclic if \\(G[S]\\), the subgraph it spans, is a forest; \\(a(G)\\) denotes the maximum cardinality of an acyclic set in \\(G\\). \\(\\dot K_4\\) is the graph obtained from \\(K_4\\) by subdividing an edge; \\({\\mathcal F}(t,k)\\) denotes the family of connected graphs with maximum degree 3 obtained by adding edges to the disjoint union of \\(t\\) triangles and \\(k\\) copies of \\(\\dot K_4\\) so that the multigraph obtained by contracting each triangle and each copy of \\(\\dot K_4\\) to a single vertex is a tree of order \\(t+k\\) (without multiple edges); \\({\\mathcal F}\\) is the union of all \\({\\mathcal F}(t,k)\\) where \\(t\\) and \\(k\\) take on all non-negative values such that \\(t+k>0\\). A lower bound for \\(a(G)\\) is known from \\textit{N. Alon, J. Kahn} and \\textit{P. D. Seymour} [Large induced degenerate subgraphs, Graphs Comb. 3, 203-211 (1987; Zbl 0624.05039)]. NEWLINENEWLINENEWLINEThis paper was motivated by a conjecture of M. Albertson and R. Haas: If \\(G\\) is an \\(n\\)-vertex planar bipartite graph, then \\(a(G)\\geq\\frac 58n\\). The authors begin by proving Lemma 2.1: If \\(G=(V,E)\\) is a triangle-free graph, then \\(a(G)\\geq |V|-\\frac {|E|}4\\). Theorem 1.5: If exactly \\(c\\) components of a \\(K_4\\)-free graph \\(G\\) with maximum degree 3 are from \\({\\mathcal F}\\), then \\(a(G)\\geq|V|-\\frac{|E|}4-\\frac c4\\). Corollary 1.7: If \\(G\\) is an \\(n\\)-vertex triangle-free graph with maximum degree 3, then \\(a(G)\\geq\\frac{5n}8\\), and the inequality is sharp whenever \\(8|n\\). Theorem 1.7: Let \\(G=(V,E)\\) be a connected graph with maximum degree \\(\\Delta\\geq 3\\). Then \\(a(G)\\geq\\alpha(G)+\\frac{|V|-\\alpha(G)}{(\\Delta-1)^2}\\) (where \\(\\alpha\\) denotes the independence number). In \\S 4 the authors construct \\(n\\)-vertex \\(\\Delta\\)-regular bipartite graphs \\(G_{a,b}\\) (where \\(ab=n\\)) with \\(a(G)\\leq \\frac n2+{\\mathcal O}(\\frac n{\\Delta^2})\\) as \\(n\\to\\infty\\). Theorem 4.3: \\(a(G_{a,b})\\leq ab+1\\). Corollary 4.4: For integers \\(\\Delta\\), \\(n\\), where \\(\\left\\lfloor(\\Delta+1)^2/2\\right\\rfloor|n\\), there exists an \\(n\\)-vertex \\(\\Delta\\)-regular bipartite graph with \\(a(G)=\\frac n2+\\frac{n}{\\lfloor\\frac{(\\Delta+1)^2}2\\rfloor}\\). If \\((2\\Delta)|n\\), then there exists an \\(n\\)-vertex \\(\\Delta\\)-regular bipartite graph with \\(a(G)=\\frac n2+\\frac n{2\\Delta}\\). Remark 4.5: The graphs \\(G_{a,b}\\) also provide our best constructions for 4-regular and 5-regular bipartite graphs with no large acyclic sets. In particular, Theorem 4.3 immediately yields \\(a(G_{2,3})=7\\), and \\(a(G_{3,3})=10\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2781059$36A0230E-5904-407F-BA7F-BB382C37D0BD","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":"Q2781059$9738E145-74AC-4009-9290-37A8DC65E55E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e5fab73d07a2d93ec3de8cd632ea7590fa4a9de","datavalue":{"value":{"entity-type":"item","numeric-id":2494123,"id":"Q2494123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a617398515c6ab32cbb4e3d61b4cec097a4b1eb","datavalue":{"value":{"amount":"+0.8359264135360718","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":"Q2781059$AB3ED2AC-4D5C-4D2A-8B0A-14418A292B1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e10bfe43ec847a17c8c493f1531850b3e0431791","datavalue":{"value":{"entity-type":"item","numeric-id":4978444,"id":"Q4978444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a0696382b546ad86e465aa0d9fe4fe204c27f74","datavalue":{"value":{"amount":"+0.8205477595329285","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":"Q2781059$7EC96386-53AA-4EE5-8456-8202025981A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a70508b6fb5ec32d4f88eab3530a2ee401438dcf","datavalue":{"value":{"entity-type":"item","numeric-id":501988,"id":"Q501988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19d9ec220c91d7224846e5ebff32ac9b20a6075c","datavalue":{"value":{"amount":"+0.8036451935768127","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":"Q2781059$1065DA26-27EC-4287-A157-03AE78B1B910","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75a1759927ae3a1d639df6fb0e776c47e7adfea8","datavalue":{"value":{"entity-type":"item","numeric-id":1417566,"id":"Q1417566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8517f9ba706b6d474cd2ba75f7045b9bfd839f2","datavalue":{"value":{"amount":"+0.8015806674957275","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":"Q2781059$F312AD66-1E0A-4284-BA1F-70528E833F83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1402505e26a1d60585f56a08a94f2fd89cafdabe","datavalue":{"value":{"entity-type":"item","numeric-id":5441408,"id":"Q5441408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee1574ada8a1a94a9e8f1982a3a3606f5f0bb63f","datavalue":{"value":{"amount":"+0.7985749840736389","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":"Q2781059$3B8705CB-1FE3-4A98-B3B4-B67A1BC7493F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2781059","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2781059"}}}}}