Extended formulations for induced tree and path polytopes of chordal graphs

Alexandre Dupont-Bouillard

REVIEW 4 major objections 6 minor 19 references

Extended formulations for induced tree and path polytopes of chordal graphs

T0 review · 4 major / 6 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For chordal graphs, this paper proves that the extended incidence vectors of induced trees and of induced paths form Hilbert bases, so both polytopes have compact extended formulations and weighted optimization is polynomial-time.

desk verdict Solid new Hilbert-basis results for induced tree/path polytopes in chordal graphs; proofs essentially correct, but the write-up has a few typos and one terse contraction step that needs a clearer justification. read the letter →

arxiv 2512.08554 v4 pith:DZ6ROPCK submitted 2025-12-09 cs.DM

Alexandre Dupont-Bouillard This is my paper · ORCID

classification cs.DM MSC 90C2705C7552B12

keywords inducedtreespathschordalgraphsHilbertbasisextendedformulationsintegerdecompositionpropertypolyhedralcombinatoricspolytopes

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks when the convex hulls of induced trees and induced paths admit simple, small linear descriptions. The answer it proves: in a chordal graph, the cone generated by the extended incidence vectors (vertices plus edges) of induced trees, and likewise of induced paths, is generated by those incidence vectors as a Hilbert basis — every integer point of the cone is a nonnegative integer combination of them. Cutting that cone with the single hyperplane x(V)-y(E)=1 then yields the induced tree polytope and the induced path polytope exactly, and the paper shows this description is exact precisely for chordal graphs. The consequences are algorithmic: both polytopes have the integer decomposition property, the induced-path formulation collapses to O(|V|^2) non-dominated inequalities, and weighted maximum induced tree and induced path problems become polynomial-time solvable on chordal graphs.

What carries the argument

The load-bearing objects are the extended incidence vectors ξ_W = (χ_W, ζ_E(W)), which encode an induced tree or path by both its vertices and its edges, and the Hilbert-basis property: every integer point of the cone C_T(G) or C_P(G) is a nonnegative integer combination of such vectors. The cone descriptions matter. C_T(G) uses one inequality per vertex and incident maximal clique, enforcing that an induced tree never has two edges from the same vertex into one triangle; C_P(G) uses inequalities (5) that count edges incident to a vertex against a clique K in its neighborhood, with edges to C(K∪{w}) counted once and edges to K counted twice. The proofs proceed by induction on a simplicial ve

What would settle it

The theorems predict that for any chordal graph the polytope T(G) or P(G) has only binary extreme points and that every integer point of the cone is an integer conic combination of incidence vectors. A single counterexample to either statement — found by brute-force enumeration on small chordal graphs, or a non-chordal graph for which T(G) or P(G) is nonetheless binary — would refute the characterization. A more surgical check: search for two induced paths in a chordal graph sharing an endpoint whose second vertices are nonadjacent and whose union is not an induced path; such a pair would viol

Watch

Extended reading notes

Core claim

The central claim is a Hilbert-basis theorem for chordal graphs. For the induced tree cone C_T(G), defined by inequalities that forbid a vertex from sending two edges into any triangle of a maximal clique, the extended incidence vectors of induced trees form a Hilbert basis (Theorem 1.1); the identical statement holds for the induced path cone C_P(G), defined by inequalities (5) that bound weighted sums of edges incident to each vertex, with the path incidence vectors forming a Hilbert basis (Theorem 2.11). In both cases, intersecting the cone with the hyperplane x(V)-y(E)=1 gives a polytope whose binary points are exactly the incidence vectors of induced trees or induced paths. The paper pr

Load-bearing premise

The load-bearing premise is that two induced paths in a chordal graph that share an endpoint can always be recombined cleanly: either their second vertices are adjacent, or the union of the two paths is again an induced path; the whole path Hilbert-basis argument rests on this recombination fact and on the edge-contraction argument that proves it.

Editorial extensions

If this is right

For every chordal graph, the induced tree polytope is the intersection of C_T(G) with x(V)-y(E)=1; since C_T(G) has O(|V||K|) inequalities, the maximum-weight induced tree problem is solvable in polynomial time.
For every chordal graph, the induced path polytope is the intersection of C_P(G) with the same hyperplane; despite the exponential naive system, the non-dominated inequalities number O(|V|^2), so a compact extended formulation exists and the maximum-weight induced path problem is polynomial-time solvable.
Both polytopes have the integer decomposition property in chordal graphs, meaning every integer point of k times the polytope is a sum of k incidence vectors of induced trees or induced paths.
An inequality (5) is facet-defining exactly when no connected component of G[C(K∪{w})] is bipartite, which tells which of the exponentially many path inequalities are actually essential.
The characterization is sharp: if G is not chordal, T(G) and P(G) are not binary, so the simple hyperplane description itself detects chordality.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The Hilbert-basis route likely extends beyond chordal graphs: the paper notes C4 already satisfies it, so the exact class of graphs with Hilbert bases is larger and may have a forbidden-induced-subgraph characterization; a natural next step is to identify it.
The facet characterization of inequalities (5) suggests a polynomial-time separation routine for the compact path formulation, which the paper does not spell out but which would make the extended formulation directly usable in cutting-plane solvers.
The same recipe — prove a Hilbert basis for the cone of incidence vectors of a hereditary family, then cut with x(V)-y(E)=1 — could yield compact extended formulations for other induced subgraph polytopes, such as induced forests, on graph classes with a similar elimination structure.
Because T(G) and P(G) are binary exactly on chordal graphs, one can read the theorem as a polyhedral certificate of chordality: linear programming over these simple systems detects whether a graph is chordal, independent of graph-theoretic recognition algorithms.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take. The result is real: this is the first compact extended formulation for induced tree and path polytopes on chordal graphs, and the Hilbert-basis / IDP part is the core. The proofs are constructive and the cone descriptions are natural. I gave the long path proof a close read; the reorganization argument in Theorem 2.11 is intricate but I believe it holds. The facet characterization and the O(|V|^2) bound on non-dominated inequalities are nice contributions.

The soft spots are mostly presentation. Theorem 1.3 writes the non-chordal point with x_w=1 on all of V\v; that makes the hyperplane count fail unless the hole spans all vertices. It should be the hole vertices only. At the end of Theorem 2.15 the rank is given as |V|+|E| but the dimension is |V|+|E|-1; the count is off by one. Some implicit assumptions need stating: every vertex can be last in a PEO (they cite Dirac, fine), and the contraction in Claim 2.2 assumes the vertex set P1∪P2 minus {u,u1,u2} is connected. That connectivity is not explicitly justified, but I don't think it's a real gap. The stress-test counterexample does not survive: in their example P2 has u and u1 nonconsecutive while the edge u-u1 exists in G because P1 contains it, so P2 is not induced; and the graph is not chordal. If the union of two induced paths sharing an endpoint fails to be a path, you get a cycle containing u,u1,u2, and the rest of the cycle plus any branches attaches to vertices of that cycle other than u1,u2, so the contracted set is connected. The proof of Claim 2.2 should spell this out, but the claim stands.

The tree-side proof is sound and doesn't depend on Claim 2.2. The paper is honest about the exponential path system and the redundant inequalities in the polynomial superset. I found no fit-to-conclusion problem; the cones are defined independently and the Hilbert-basis proofs actually generate them.

Who is this for? Polyhedral combinatorics people, especially those working on structured graph polytopes and IDP. It deserves a serious referee, and it should be publishable after revision. I'd bring it to a reading group and I'd cite it.

Referee Report

4 major / 6 minor

Summary. The paper defines extended incidence vectors for induced trees and induced paths of a graph, together with cones C_T(G) and C_P(G). It claims that for chordal graphs these incidence vectors form Hilbert bases (Theorems 1.1 and 2.11), and that intersecting the cones with x(V)-y(E)=1 yields binary polytopes T(G) and P(G), so that chordality is equivalent to integrality (Theorems 1.3 and 2.13). It also characterizes the facet-defining inequalities among those of C_P(G) (Theorem 2.15), proves a quadratic bound on the non-dominated such inequalities (Theorem 2.16), and concludes polynomial-time solvability for maximum-weight induced tree and induced path on chordal graphs.

Significance. If the Hilbert-basis results are correct, the paper gives a compact extended formulation for the induced tree polytope and an exponential—but polynomially enumerable—extended formulation for the induced path polytope of chordal graphs, with the integer decomposition property as a byproduct. The tree-side proof (Theorem 1.1) is self-contained and plausible, and the cone C_T is defined independently of the claimed generating set, so this part is a genuine contribution. The path-side proof, however, rests on Claim 2.2, whose proof is incomplete, and the facet characterization in Theorem 2.15 appears to be false as stated. These issues undermine two of the main advertised contributions.

major comments (4)

[§2.1, Claim 2.2] The proof contracts all edges in E(P1∪P2\{u1,u2,u}) to a single vertex w. Such a contraction collapses the set S = V(P1∪P2)\{{u,u1,u2}} only if G[S] is connected. The manuscript does not prove connectivity, and it is not a formal consequence of the preceding sentences. For example, if P1 = u-u1-a and P2 = u-u2-b-u1-c, then S = {a,b,c} has no edges among its vertices (this particular graph is not chordal, but it shows the missing argument is nontrivial). Since Claim 2.2 is invoked in Lemmas 2.7 and 2.10 and in the K_Ψ reorganization step of Theorem 2.11, the Hilbert-basis proof for induced paths is incomplete as written. The author needs either to prove that G[S] is connected under the chordal hypotheses or to replace the contraction with a different argument before Theorem 2.11 can be accepted.
[§2.2, Theorem 2.15] The characterization is false as stated. Take G = K5, let w=1 and K={2}. Then C(K∪{w}) = {3,4,5}, and G[C(K∪{w})] = K3, which has no bipartite connected component, so the stated condition holds. Inequality (5) is 2y_{12} + y_{13} + y_{14} + y_{15} ≤ 2x_1. The extreme points of P(G) for K5 are the 5 singletons and 10 edges. Those satisfying equality are the four singletons not containing 1, the six edges among {2,3,4,5}, and the edge {1,2}, for a total of 11 vertices. Since P(G) has dimension 14 (its affine hull is exactly x(V)-y(E)=1), a facet requires 14 affinely independent vertices; a face with only 11 vertices cannot be a facet. Thus the 'if' direction of Theorem 2.15 is contradicted by a chordal graph.
[§2.2, Theorem 2.15 proof, 'if' direction] Even setting aside the K5 counterexample, the construction of the remaining tight points is invalid. The proof matches each edge uw ∈ δ(w, C(K∪{w})) to an edge uv ∈ T ⊆ E(G[C(K∪{w})]). But then u and v are adjacent in G, so the set {u,w,v} induces a triangle, not an induced path. The text asserts that u and v are non-adjacent, which contradicts the choice of uv as an edge of T. The proof therefore does not produce the required |δ(w,C(K∪{w}))| additional tight extreme points. The statement may need to be reformulated using the complement of G[C(K∪{w})], but as written both the statement and the proof are incorrect.
[§2.2, Theorem 2.15 proof, 'only if' direction] The domination argument also contains a gap. The proof asserts that K_j = (∪_{i=1}^ℓ S^j_i) ∪ K ∪ {w} is a clique, where S^j_i are the two stable sets of a bipartite component G_i of G[C(K∪{w})]. However, S^j_i is a stable set, so its elements are pairwise nonadjacent, and vertices from different connected components are nonadjacent by definition of components. Hence the union is generally not a clique. This invalidates the claimed domination of the inequality by two other inequalities and further indicates that the facet analysis in Theorem 2.15 needs substantial revision.

minor comments (6)

[Definitions] In the notation section, 'G\uv¨' appears to be a typo for 'G\uv'.
[Proof of Theorem 1.1] In the induction step, 'nonnegative integer combination of induced paths’ extended incidence vectors' should read 'induced trees’ extended incidence vectors'.
[Figure 1 caption] The caption refers to 'the proof of Theorem 1.3', but the figure is used in the proof of Theorem 1.1.
[Conjecture 2.4 / Theorem 2.11] Conjecture 2.4 is immediately proved as Theorem 2.11 in the same section. It would be clearer to present it as a statement or proposition, not a conjecture.
[Proof of Theorem 2.15] The proof says the whole matrix has rank |V|+|E|, but only |V|+|E|-1 rows are constructed. The correct target rank is |V|+|E|-1, matching the dimension of the polytope.
[Section 2.2] Minor typos include 'initilization' for 'initialization' and several missing or duplicated words.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the Hilbert-basis proofs are self-contained; the only author self-citation is an external, parameter-free contraction-closure lemma that is not equivalent to the target results.

full rationale

The paper's derivation chain is not circular. The cones C_T(G) and C_P(G) are defined by explicit linear inequalities, and the extended incidence vectors of induced trees and induced paths are shown, by induction and by an extremal/minimization argument, to form Hilbert bases of those cones. There are no fitted parameters, no reverse-engineered constants, and no quantity called a prediction that is actually an input. The polytope descriptions then follow by intersecting the cones with the hyperplane x(V)-y(E)=1, and the if-and-only-if chordality statements are proven directly, including explicit non-binary points for graphs containing a hole. The only author-overlapping citation is Lemma 2.1, taken from [18], which states that chordal graphs are closed under edge contraction. This lemma is used in Claim 2.2 and hence in the path Hilbert-basis proof, but it is a parameter-free external theorem whose stated assumptions do not include the Hilbert-basis or polytope conclusions, so under the review rules it counts as independent support rather than load-bearing circularity. Concerns about whether Claim 2.2's contraction step adequately establishes connectivity, or about other proof details, are correctness risks, not circularity: they do not amount to a step in which an output is equivalent to an input by construction. No self-definitional, fitted-input, imported-uniqueness, ansatz-smuggling, or known-result-renaming pattern is present.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters or invented entities. The central claim rests on standard chordal-graph facts, standard polyhedral-cone facts, and one self-cited contraction theorem [18]; all are external assumptions rather than fitted or postulated objects.

assumptions (6)

standard math Chordal graphs have a simplicial vertex; equivalently, a perfect elimination ordering exists.
Used to drive induction in Theorems 1.1 and 2.11 and to bound T(G) in Theorem 1.3.
standard math Chordal graphs are closed under edge contraction (Lemma 2.1, cited [18]).
Used in Claim 2.2 and therefore throughout the path Hilbert-basis proof §2.1.
standard math Every vertex of a chordal graph can be chosen as the last vertex of a perfect elimination ordering.
Invoked in Theorem 1.3 to derive x_v≤1 for every vertex v; not stated or proved in the paper.
standard math For a cone defined by rational inequalities, each 1-dimensional face contains integer points, so a Hilbert basis of the cone generates it.
Used in Theorem 1.3 to pass from a Hilbert basis of C_T(G) to extreme points of T(G).
standard math Every connected non-bipartite graph contains a spanning unicyclic subgraph with exactly |V| edges whose unique cycle is odd.
Used in Theorem 2.15 to construct tight points for the facet proof; not stated as a lemma.
standard math The unoriented incidence matrix of a graph has full row rank iff every connected component is non-bipartite (Thm 2.1 of [19]).
Used to conclude non-singularity of the H block in Theorem 2.15.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Extended formulations for induced tree and path polytopes of chordal graphs." pith.science (2026). https://pith.science/paper/DZ6ROPCK

@misc{pith2026251208554,
  author       = {Pith},
  title        = {Pith review of: Extended formulations for induced tree and path polytopes of chordal graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DZ6ROPCK}},
  note         = {Machine review of arXiv:2512.08554}
}

read the original abstract

In this article, we give two extended space formulations, respectively, for the induced tree and path polytopes of chordal graphs with vertex and edge variables. These formulations are obtained by proving that the induced tree and path extended incidence vectors of chordal graphs form Hilbert basis. This also shows that both polytopes have the integer decomposition property in chordal graphs. Whereas the formulation for the induced tree polytope is easily seen to have a compact size, the system we provide for the induced path polytope has an exponential number of inequalities. We show which of these inequalities define facets and exhibit a superset of the facet-defining ones that can be enumerated in polynomial time. We show that for some graphs, the latter superset contains redundant inequalities. As corollaries, we obtain that the problems of finding an induced tree or path maximizing a linear function over the edges and vertices are solvable in polynomial time for the class of chordal graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 7 canonical work pages

[1]

4OR (2010)

Conforti, M., Cornu´ ejols, G., Zambelli, G.: Extended formulations in combinato- rial optimization. 4OR (2010)

2010
[2]

Journal of Combinatorial Theory, Series B41(1), 61–79 (1986) https://doi.org/10.1016/ 0095-8956(86)90028-6

Erd¨ os, P., Saks, M., S´ os, V.T.: Maximum induced trees in graphs. Journal of Combinatorial Theory, Series B41(1), 61–79 (1986) https://doi.org/10.1016/ 0095-8956(86)90028-6

1986
[3]

Electronic Notes in Discrete Mathematics29, 307–313 (2007) https://doi.org/10.1016/j.endm.2007

Matouˇ sek, J.,ˇS´ amal, R.: Induced trees in triangle-free graphs. Electronic Notes in Discrete Mathematics29, 307–313 (2007) https://doi.org/10.1016/j.endm.2007. 07.053 . European Conference on Combinatorics, Graph Theory and Applications

work page doi:10.1016/j.endm.2007 2007
[4]

Journal of Combinatorial Theory, Series B99(2), 494–501 (2009) https://doi.org/10.1016/ j.jctb.2008.10.001

Fox, J., Loh, P.-S., Sudakov, B.: Large induced trees in kr-free graphs. Journal of Combinatorial Theory, Series B99(2), 494–501 (2009) https://doi.org/10.1016/ j.jctb.2008.10.001

2009
[5]

Jour- nal of Graph Theory38(3), 113–123 (2001) https://doi.org/10.1002/jgt.1028 19 https://onlinelibrary.wiley.com/doi/pdf/10.1002/jgt.1028

Alon, N., Mubayi, D., Thomas, R.: Large induced forests in sparse graphs. Jour- nal of Graph Theory38(3), 113–123 (2001) https://doi.org/10.1002/jgt.1028 19 https://onlinelibrary.wiley.com/doi/pdf/10.1002/jgt.1028

doi:10.1002/jgt.1028 2001
[6]

Journal of Computer and System Sciences (1978)

Yannakakis, M.: The node deletion problem for hereditary properties. Journal of Computer and System Sciences (1978)

1978
[7]

International Transactions in Operational Research29(4), 2263–2287 (2022) https://doi.org/10.1111/itor

Melo, R.A., Ribeiro, C.C.: Maximum weighted induced forests and trees: new formulations and a computational comparative review. International Transactions in Operational Research29(4), 2263–2287 (2022) https://doi.org/10.1111/itor. 13066 https://onlinelibrary.wiley.com/doi/pdf/10.1111/itor.13066

work page doi:10.1111/itor 2022
[8]

IRE Trans

Kautz, W.H.: Unit-distance error-checking codes. IRE Trans. Electron. Comput., 179–180 (1958)

1958

Show all 19 references

[9]

European Journal of Combinatorics, 1–14 (2017)

Esperet, L., Lemoine, L., Maffray, F.: Long induced paths in graphs. European Journal of Combinatorics, 1–14 (2017)

2017
[10]

https://arxiv.org/abs/2412.14863

Duron, J., Esperet, L., Raymond, J.-F.: Long induced paths and forbidden patterns: Polylogarithmic bounds (2025). https://arxiv.org/abs/2412.14863

2025
[11]

Information Pro- cessing Letters81(4), 203–208 (2002) https://doi.org/10.1016/S0020-0190(01) 00222-8

Gavril, F.: Algorithms for maximum weight induced paths. Information Pro- cessing Letters81(4), 203–208 (2002) https://doi.org/10.1016/S0020-0190(01) 00222-8

2002 doi
[12]

Discrete Optimization 6(2), 135–147 (2009) https://doi.org/10.1016/j.disopt.2008.10.004

Hansen, P., Labb´ e, M., Schindl, D.: Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results. Discrete Optimization 6(2), 135–147 (2009) https://doi.org/10.1016/j.disopt.2008.10.004

2009 doi
[13]

Lecture Notes in Computer Science (2003)

Dieter, K., Haiko, M., Ioan, T.: Feedback vertex set and longest induced path on at-free graphs. Lecture Notes in Computer Science (2003)

2003
[14]

https://arxiv.org/abs/2502.21204

Goel, A., Maraj, A., Ribot, A.: Halfspace Representations of Path Polytopes of Trees (2025). https://arxiv.org/abs/2502.21204

2025 arXiv
[15]

European Journal of Oper- ational Research278(2), 546–562 (2019) https://doi.org/10.1016/j.ejor.2019.04

Matsypura, D., Veremyev, A., Prokopyev, O.A., Pasiliao, E.L.: On exact solution approaches for the longest induced path problem. European Journal of Oper- ational Research278(2), 546–562 (2019) https://doi.org/10.1016/j.ejor.2019.04. 011

2019 doi
[16]

RAIRO-Oper

Marzo, Rusl´ an G., Ribeiro, Celso C.: Exact and approximate algorithms for the longest induced path problem. RAIRO-Oper. Res.55(2), 333–353 (2021) https: //doi.org/10.1051/ro/2021004

2021
[17]

Abhandlungen aus dem Mathematischen Seminar der Universit¨ at Hamburg25, 71–76 (1961) https://doi.org/10.1007/ BF02992776

Dirac, G.A.: On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universit¨ at Hamburg25, 71–76 (1961) https://doi.org/10.1007/ BF02992776

1961
[18]

Discrete Applied Mathematics377, 380–389 (2025) https://doi

Dupont-Bouillard, A., Fouilhoux, P., Grappe, R., Lacroix, M.: Contractions in perfect graphs. Discrete Applied Mathematics377, 380–389 (2025) https://doi. 20 org/10.1016/j.dam.2025.07.022

2025 doi
[19]

Linear Algebra and its Applications 218, 213–224 (1995) https://doi.org/10.1016/0024-3795(93)00173-W 21

Grossman, J.W., Kulkarni, D.M., Schochetman, I.E.: On the minors of an inci- dence matrix and its smith normal form. Linear Algebra and its Applications 218, 213–224 (1995) https://doi.org/10.1016/0024-3795(93)00173-W 21

1995 doi

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1]

4OR (2010)

Conforti, M., Cornu´ ejols, G., Zambelli, G.: Extended formulations in combinato- rial optimization. 4OR (2010)

2010

[2] [2]

Journal of Combinatorial Theory, Series B41(1), 61–79 (1986) https://doi.org/10.1016/ 0095-8956(86)90028-6

Erd¨ os, P., Saks, M., S´ os, V.T.: Maximum induced trees in graphs. Journal of Combinatorial Theory, Series B41(1), 61–79 (1986) https://doi.org/10.1016/ 0095-8956(86)90028-6

1986

[3] [3]

Electronic Notes in Discrete Mathematics29, 307–313 (2007) https://doi.org/10.1016/j.endm.2007

Matouˇ sek, J.,ˇS´ amal, R.: Induced trees in triangle-free graphs. Electronic Notes in Discrete Mathematics29, 307–313 (2007) https://doi.org/10.1016/j.endm.2007. 07.053 . European Conference on Combinatorics, Graph Theory and Applications

work page doi:10.1016/j.endm.2007 2007

[4] [4]

Journal of Combinatorial Theory, Series B99(2), 494–501 (2009) https://doi.org/10.1016/ j.jctb.2008.10.001

Fox, J., Loh, P.-S., Sudakov, B.: Large induced trees in kr-free graphs. Journal of Combinatorial Theory, Series B99(2), 494–501 (2009) https://doi.org/10.1016/ j.jctb.2008.10.001

2009

[5] [5]

Jour- nal of Graph Theory38(3), 113–123 (2001) https://doi.org/10.1002/jgt.1028 19 https://onlinelibrary.wiley.com/doi/pdf/10.1002/jgt.1028

Alon, N., Mubayi, D., Thomas, R.: Large induced forests in sparse graphs. Jour- nal of Graph Theory38(3), 113–123 (2001) https://doi.org/10.1002/jgt.1028 19 https://onlinelibrary.wiley.com/doi/pdf/10.1002/jgt.1028

doi:10.1002/jgt.1028 2001

[6] [6]

Journal of Computer and System Sciences (1978)

Yannakakis, M.: The node deletion problem for hereditary properties. Journal of Computer and System Sciences (1978)

1978

[7] [7]

International Transactions in Operational Research29(4), 2263–2287 (2022) https://doi.org/10.1111/itor

Melo, R.A., Ribeiro, C.C.: Maximum weighted induced forests and trees: new formulations and a computational comparative review. International Transactions in Operational Research29(4), 2263–2287 (2022) https://doi.org/10.1111/itor. 13066 https://onlinelibrary.wiley.com/doi/pdf/10.1111/itor.13066

work page doi:10.1111/itor 2022

[8] [8]

IRE Trans

Kautz, W.H.: Unit-distance error-checking codes. IRE Trans. Electron. Comput., 179–180 (1958)

1958