Large induced subgraph with a given pathwidth in outerplanar graphs

Hikaru Yokoi; Naoki Matsumoto; Takamasa Yashima

REVIEW 2 major objections 5 minor 14 references

Large induced subgraph with a given pathwidth in outerplanar graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper pins down the size of the largest induced subgraph of bounded pathwidth in an outerplanar graph: at least $M_k n/(M_k+3)$ vertices, and at most $M_k n/(M_k+4/3)$ in a construction, with $M_k$ the largest order forcing pathwidth…

desk verdict A solid extension of Pelsmajer's induced-linear-forest theorem to higher pathwidth; the proof gap in Theorem 4 is a repairable index typo, not a structural flaw. read the letter →

arxiv 2505.23162 v2 pith:HV6ZYHHC submitted 2025-05-29 cs.DM math.CO

Naoki Matsumoto , Takamasa Yashima , Hikaru Yokoi This is my paper

classification cs.DMmath.CO MSC 05C1005C70

keywords pathwidthouterplanargraphsinducedsubgraphstreewidthlinearforestsextremalgraphtheorydecompositionsAlbertson-Bermanconjecture

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

The paper asks how many vertices of an outerplanar graph can be kept in an induced subgraph once the subgraph is required to have bounded pathwidth, a measure of how path-like a graph is. For each fixed $k$ it proves a uniform answer: letting $M_k$ be the largest $t$ such that every outerplanar graph on at most $t$ vertices has pathwidth at most $k$, every outerplanar graph of order $n$ contains an induced subgraph of pathwidth at most $k$ with at least $M_k n/(M_k+3)$ vertices, and for $k=2$ the ratio improves to $5n/7$. The paper also constructs outerplanar graphs in which no such induced subgraph has more than $M_k n/(M_k+4/3)$ vertices, so the two constants are close and the whole problem collapses to the sequence $M_k$. This generalizes a known sharp bound for induced linear forests (pathwidth 1) to every pathwidth, leaving only the gap between the two constants.

What carries the argument

The controlling object is the sequence $M_k$: the largest $t$ for which every outerplanar graph with at most $t$ vertices has pathwidth at most $k$, with $M_1=2$, $M_2=5$, and $M_3 \leq 23$. The lower bound is carried by an inductive face-splitting argument that peels a component of order just above $M_k$ and uses the fact that a disconnected union of two subgraphs each of order below $M_k$ still has pathwidth at most $k$. The upper bound is carried by a deliberately assembled obstruction: three $(M_k+1)$-vertex outerplanar blocks of pathwidth at least $k+1$ sharing one central vertex $x$, so that any width-$k$ induced subgraph is forced to leave at least one vertex out of each block. The interval property of path-decompositions — that any vertex appearing in two bags appears in every bag between them — is what prevents the blocks' largest bags from overlapping with $x$'s bags beyond the allowed width.

What would settle it

For $k=2$, take the 19-vertex construction of Theorem 4 (three 6-vertex maximal outerplanar graphs of pathwidth 3 sharing a common vertex) and compute the maximum order of an induced subgraph of pathwidth at most 2 by exhaustive search. Theorem 4 predicts exactly 15; finding 16 refutes the upper bound. Separately, an exhaustive search over order-7 maximal outerplanar graphs would test the $5n/7$ lower bound.

Watch

Extended reading notes

Core claim

At the center of the paper is a pair of theorems that together bracket the extremal ratio. Theorem 2 states that for every outerplanar graph $G$ of order $n$ and every positive integer $k$, $I_k(G) \geq M_k n/(M_k+3)$, where $I_k(G)$ is the maximum order of an induced subgraph of $G$ with pathwidth at most $k$. The proof is an induction on maximal outerplanar graphs: it locates an edge whose removal leaves a component $H$ of order just above $M_k$, splits the graph into $G'$ and the two sides of a face, and combines the induction on $G'$ with the fact that the union of the two sides has pathwidth at most $k$. Theorem 3 sharpens the case $k=2$ to $I_2(G) \geq 5n/7$, using a lemma that every outerplanar graph with at most five vertices admits a width-2 path-decomposition with any prescribed vertex in an end bag. Theorem 4 gives the matching upper bound by gluing three copies of an $(M_k+1)$-vertex outerplanar graph of pathwidth at least $k+1$ at a common vertex $x$; the resulting graph has $3M_k+4$ vertices, and any induced subgraph of pathwidth at most $k$ can use at most $M_k$ vertices from each copy, giving $I_k \leq 3M_k$.

Load-bearing premise

The upper-bound proof depends on a placement claim about path-decompositions: a largest bag of one of the three blocks must not lie between the bags containing the shared vertex, because the interval property would then force a forbidden overlap; if this placement step fails, the construction's ratio is not established.

Editorial extensions

If this is right

For every positive integer $k$, every outerplanar graph of order $n$ has an induced subgraph of pathwidth at most $k$ with at least $M_k n/(M_k+3)$ vertices.
For $k=2$ the universal guarantee is $5n/7$, improving the general formula's $5/8$ for that case.
There exist outerplanar graphs of order $n$ where $I_k$ is at most $M_k n/(M_k+4/3)$, so the lower bound cannot be substantially improved without a new idea.
Because $M_k$ grows with $k$, both fractions approach $1$; for large $k$ nearly all vertices of any outerplanar graph can be kept in an induced subgraph of pathwidth at most $k$.
At $k=1$ the theorem's lower bound ($2/5$) is weaker than the known sharp bound of $4/7$ for induced linear forests, so the paper's contribution is the uniform statement for all $k$, not the smallest case.

Reading between the lines

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

Beyond the paper, the two bounds suggest the true extremal ratio is $M_k/(M_k+c)$ for a constant $c$ between $4/3$ and $3$; determining $c$ is equivalent to understanding how tightly the $M_k$-vertex obstruction can concentrate around a single attachment vertex.
Beyond the paper, the lower-bound proof's only graph-specific input is the facial splitting lemma; graph classes with an analogous face-separation property would inherit bounds of the same shape.
Beyond the paper, the arguments are constructive enough to yield a search algorithm for the induced subgraph once $M_k$ is known, although the paper does not state or analyze running times.
Beyond the paper, the $k=2$ gap between $5/7$ and $15/19$ can be tested by exact computation on maximal outerplanar graphs of moderate order; the extremal ratio may lie closer to $5/7$ than to the upper construction.

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

The paper does what it says: it generalizes Pelsmajer's 2004 result on induced linear forests (pathwidth 1) to arbitrary pathwidth k, introducing the invariant M_k and proving matching lower and upper bounds for outerplanar graphs. The lower-bound proofs (Theorems 2 and 3) are coherent inductions, and the upper-bound construction (Theorem 4) is a legitimate generalization of Pelsmajer's sharpness example. The M_k parameter is a natural and useful device, and the results genuinely extend the literature rather than repackaging it.

The soft spots are real but local. In the final paragraph of Theorem 4, the sentence 'Therefore, B_i must contain a vertex of V(F_i)∪{x}' has the wrong index; the path L runs from B_j^p to X_j^p, so the vertex forced into every intermediate bag lies in V(F_j)∪{x}, not V(F_i). With that correction, the interval property of path decompositions does the job, and the claimed upper bound goes through. Similarly, the displayed inequality in Theorem 3 has an off-by-two typo, but the intended bound is valid. The notation 'G-ab' should be 'G-{a,b}'; it is confusing but the meaning is clear from context.

I disagree with any reading that treats Theorem 4 as fatally flawed. The stress-test note is correct: the argument is sound once the index is fixed. This is a paper where the core mathematics holds up and the blemishes are exposition-level. I also note the paper is honest about its limits: the k=1 lower bound from Theorem 2 (2/5) is worse than Pelsmajer's 4/7, and the authors do not overclaim otherwise. The citation pattern looks appropriate, and no circularity is present.

This paper is for researchers working on induced subgraphs with bounded width parameters, especially in outerplanar and planar graphs. It gives a clean framework and an explicit open problem for planar graphs. It deserves a serious referee: the theorems are nontrivial, the proofs are mostly transparent, and the remaining issues are fixable in revision. I would accept it for peer review and recommend minor revision rather than desk rejection.

Referee Report

2 major / 5 minor

Summary. The paper studies the maximum order I_k(G) of an induced subgraph of an outerplanar graph G with pathwidth at most k. It introduces the invariant M_k, the largest t such that every outerplanar graph on at most t vertices has pathwidth at most k, and proves three main results: Theorem 2 gives the lower bound I_k(G) ≥ M_k n/(M_k+3) for every outerplanar graph of order n; Theorem 3 improves this to 5n/7 for k=2; and Theorem 4 constructs, for each admissible k, an outerplanar graph H with I_k(H) ≤ M_k n/(M_k+4/3). The proofs are inductive and use path decompositions and the outerplanar structure. The paper also discusses the relation to Pelsmajer's induced linear forest theorem and conjectures for planar graphs.

Significance. If the stated results hold, the paper provides the first general bounds for induced subgraphs of bounded pathwidth in outerplanar graphs, extending Pelsmajer's result on induced linear forests. The lower-bound proof is elementary and parameter-free, and the upper-bound construction is explicit and nearly matches the lower bound, leaving only a constant 4/3 additive gap in the denominator. The improvement for k=2 to 5/7 is concrete and new. The manuscript does not include machine-checked proofs or code, but the arguments are standard induction arguments that are likely correct once the misstatement in the final step of Theorem 4 is repaired. The results should be of interest to researchers working on induced subgraph problems and graph structure theory.

major comments (2)

[§3, Proof of Theorem 4, final paragraph] The final contradiction is misstated. The sentence 'Therefore, B_i must contain a vertex of V(F_i)∪{x}, a contradiction' is trivially true because B_i is a subset of V(F_i) by construction, so it does not contradict anything. The intended argument is that the original bag B^p_i, which lies between B^p_j and X^p_j, contains a vertex of the path L⊆V(F_j)∪{x}; since i≠j and |B_i|=k+1, the bag B^p_i would then contain at least k+2 vertices, contradicting the width of P. The same correction applies to the earlier phrase 'contradicts that x∉B_i', which should instead contradict the width bound |B^p_i|≤k+1. Theorem 4 depends on this step, so the proof must be repaired.
[§3, Proof of Theorem 3] The induction proof has no explicit base case for small n. The argument begins by choosing an edge ab such that G−{a,b} has a component H of order at least 5; for n≤8 such an H need not exist. Additionally, in the case |V(H)|=5 the induction hypothesis is applied to G' of order n−7, which can be below the theorem's stated range n≥3. The bound is likely trivially true for small n, but the proof should either verify n≤8 directly or explicitly state that the induction hypothesis is vacuously satisfied when the remaining graph has fewer than three vertices.

minor comments (5)

[§3, Proof of Theorem 2] The notation G−ab (and later G−ac, G−bc) is ambiguous; from context it must mean vertex deletion G−{a,b}, not edge deletion. Please define this shorthand, since the phrase 'component H in G−ab' and the subsequent use of V(H)∪{a,b} are otherwise inconsistent.
[§3, Proof of Theorem 3] In the displayed computation, 'I_k(G)≥5(n−7)/7+5' should be 'I_2(G)'; also 'a outerplanar graph' in the theorem statement should be 'an outerplanar graph'.
[Introduction, Table 1] The lower-bound column for k=3 reads '≤23/26', which is an upper bound on the ratio M_3/(M_3+3) given the bound M_3≤23, not a guaranteed lower bound. Since a numerical lower bound would require a lower bound on M_3, this entry should be rephrased or accompanied by a statement such as M_3≥7.
[§3, Claim 8] The reduction to the maximal outerplanar graph of order 5 is only sketched; please explain how the general case (all outerplanar graphs of order at most 5 with a distinguished vertex) follows from the single maximal example.
[§3, Proof of Theorem 4] The equality 'B_i = B^p_i' should be 'B_i = B^p_i∩V(F_i)', since P_i is obtained by restricting P to V(F_i).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the bounds follow from the inductive use of the independently defined extremal parameter M_k, and no target inequality or self-citation is assumed in its own proof.

full rationale

The paper derives its claims from a fresh extremal invariant M_k = max{t : every outerplanar graph with at most t vertices has pathwidth at most k}. This invariant is defined independently of the quantities I_k(G) being bounded, and the proofs use it only in legitimate ways: base cases and decomposition components have size at most M_k, so their pathwidth is bounded by k directly from the definition of M_k, and since induced subgraphs of outerplanar graphs are outerplanar, the definition applies. In Theorem 2 and Theorem 3, the induction does not assume the target lower bound for the main graph; it applies the induction hypothesis only to a strictly smaller graph G' and uses the definition of M_k for the removed components. The algebra then establishes the desired bound from |V(H)| >= M_k + 1 or a Claim-based end-bag decomposition. Theorem 4 constructs an upper-bound example from maximal outerplanar graphs H_i with M_k + 1 vertices and pathwidth at least k + 1; the existence of such graphs follows from the maximality of M_k, not from the theorem being proved. The subsequent argument is a standard path-decomposition interval argument. The final sentence of Theorem 4, 'Therefore, B_i must contain a vertex of V(F_i)∪{x}, a contradiction,' appears to have a typo or a local gap in the index set (it should refer to the path L in V(F_j)∪{x}), but this is a correctness/exposition issue, not circularity: the step does not assume the theorem's conclusion. The references to Pelsmajer and other prior work are used for motivation and for small-case context, not as inputs to the new proofs, and the paper contains no load-bearing self-citations. Hence there is no significant circularity in the derivation chain.

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

The central results are parameterized by M_k, a clean combinatorial invariant defined in Section 2, not a fitted constant. The proofs rely on standard monotonicity of pathwidth under edge addition and induced subgraphs, the structural face-removal property of outerplanar triangulations, and two cited results used only for the M_3 table entry. No invented entities appear.

assumptions (4)

domain assumption Pathwidth is monotone under edge addition and induced subgraph formation, and every outerplanar graph can be completed to a maximal outerplanar graph by adding edges.
Invoked at the start of the proofs of Theorems 2 and 3 to assume G is maximal outerplanar without loss of generality.
domain assumption For a maximal outerplanar graph G and an edge ab chosen as in the induction, there is an internal face abc such that removing a,c and b,c splits the component H into two components of order less than M_k.
This structural fact is stated and argued briefly in the proofs of Theorems 2 and 3, but it is not proven as a separate lemma. The falsity of this property would break the inductive step.
domain assumption The cited results of Bodlaender and Fomin and of Scheffler on the pathwidth of outerplane graphs and trees are correct and applicable.
Used in Section 1 to derive the upper bound M_3 ≤ 23 for the summary table.
domain assumption There exists a maximal outerplanar graph on M_k + 1 vertices with pathwidth at least k+1 for every k covered by Theorem 4.
The construction in Theorem 4 requires three such graphs; existence follows from the definition of M_k and monotonicity of pathwidth under edge addition, but is not explicitly proven in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Large induced subgraph with a given pathwidth in outerplanar graphs." pith.science (2026). https://pith.science/paper/HV6ZYHHC

@misc{pith2026250523162,
  author       = {Pith},
  title        = {Pith review of: Large induced subgraph with a given pathwidth in outerplanar graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HV6ZYHHC}},
  note         = {Machine review of arXiv:2505.23162}
}

abstract

A long-standing conjecture by Albertson and Berman in 1979 states that every planar graph of order $n$ has an induced forest with at least $\lceil \frac{n}{2} \rceil$ vertices. As a variant of this conjecture, Chappell conjectured that every planar graph of order $n$ has an induced linear forest with at least $\lceil \frac{4n}{9} \rceil$ vertices. As a partial solution to the conjecture, Pelsmajer in 2004 proved that every outerplanar graph of order $n$ has an induced linear forest with at least $\lceil \frac{4n+2}{7}\rceil$ vertices and this bound is sharp. In this paper, we investigate the order of induced subgraphs with a given pathwidth in outerplanar graphs. The above result of Pelsmajer implies that every outerplanar graph of order $n$ has an induced subgraph with pathwidth at most 1 and at least $\lceil \frac{4n+2}{7}\rceil$ vertices. We extend this to obtain a result on the maximum order of induced subgraphs with a given pathwidth in an outerplanar graph. We also give its upper bound, which generalizes Pelsmajer's construction.

Figures

Figures reproduced from arXiv: 2505.23162 by the authors.

**Figure 1.** The graph H Let F be the maximum induced subgraph of H with pw(F) ≤ k. It suffices to prove |V (F)| ≤ 3Mk. Suppose to the contrary that |V (F)| ≥ 3Mk + 1. By the definition of H and Hi , any induced subgraph D in H with pw(D) ≤ k has at most Mk vertices of each Hi , and so, F contains exactly Mk vertices of each Hi and the vertex x; thus, |V (F)| = 3Mk + 1. Let Fi = H[V (Hi) ∩ V (F)] for each i ∈ {1, 2, 3}, where H[… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

Akiyama and M

J. Akiyama and M. Watanabe, Maximum induced forests of planar graphs,Graphs Combin.3(1987) 201–202

work page 1987
[2]

Albertson and D.M

M.O. Albertson and D.M. Berman, A conjecture on planar graphs,Graph Theory and Related Topics (J.A. Bondy and U.S.R. Murty, eds.), Academic Press, New York (1979), 357

work page 1979
[3]

Bodlaender, A tourist guide through treewidth,Acta cybernet.11(1993), 1–21

H.L. Bodlaender, A tourist guide through treewidth,Acta cybernet.11(1993), 1–21

work page 1993
[4]

Bodlaender and F.V

H.L. Bodlaender and F.V. Fomin, Approximation of pathwidth of outerplanar graphs, J. Algorithms43(2002), 190–200

work page 2002
[5]

Borodin, On acyclic colorings of planar graphs,Discrete Math.25(1979), 211– 236

O.V. Borodin, On acyclic colorings of planar graphs,Discrete Math.25(1979), 211– 236

work page 1979
[6]

Chappell and M.J

G.G. Chappell and M.J. Pelsmajer, Maximum induced forests in graphs of bounded treewidth,Electron. J. Combin.20, Article #P8

work page
[7]

Dross, M

F. Dross, M. Montassier and A. Pinlou, Large induced forests in planar graphs with girth 4,Discrete Appl. Math.254(2019), 96–106

work page 2019
[8]

Groenland, G

C. Groenland, G. Joret, W. Nadara and B. Walczak, Approximating pathwidth for graphs of small treewidth,ACM Trans. Algorithms19(2023), 1–19

work page 2023

Show all 14 references

[9]

Hosono, Induced forests in trees and outerplanar graphs,Proc

K. Hosono, Induced forests in trees and outerplanar graphs,Proc. Fac. Sci. Tokai Univ.25(1990) 27–29

1990
[10]

Kinnersley and M.A

N.G. Kinnersley and M.A. Langston, Obstruction set isolation for the gate matrix layout problem,Discrete Appl. Math.54(1994), 169–213

1994
[11]

Korach and N

E. Korach and N. Solel, Tree-width, path-width, and cutwidth,Discrete Appl. Math. 43(1993), 97–101

1993
[12]

Pelsmajer, Maximum induced linear forests in outerplanar graphs,Graphs Com- bin.20(2004), 121–129

M.J. Pelsmajer, Maximum induced linear forests in outerplanar graphs,Graphs Com- bin.20(2004), 121–129

2004
[13]

Robertson and P.D

N. Robertson and P.D. Seymour, Graph minors. I. Excluding a forest,J. Combin. Theory Ser. B35(1983), 39–61

1983
[14]

Scheffler, A linear algorithm for the pathwidth of trees,Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel, Heidelberg: Physica-Verlag HD (1990), 613–620

P. Scheffler, A linear algorithm for the pathwidth of trees,Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel, Heidelberg: Physica-Verlag HD (1990), 613–620. 8

1990

Pith tools

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

[1] [1]

Akiyama and M

J. Akiyama and M. Watanabe, Maximum induced forests of planar graphs,Graphs Combin.3(1987) 201–202

work page 1987

[2] [2]

Albertson and D.M

M.O. Albertson and D.M. Berman, A conjecture on planar graphs,Graph Theory and Related Topics (J.A. Bondy and U.S.R. Murty, eds.), Academic Press, New York (1979), 357

work page 1979

[3] [3]

Bodlaender, A tourist guide through treewidth,Acta cybernet.11(1993), 1–21

H.L. Bodlaender, A tourist guide through treewidth,Acta cybernet.11(1993), 1–21

work page 1993

[4] [4]

Bodlaender and F.V

H.L. Bodlaender and F.V. Fomin, Approximation of pathwidth of outerplanar graphs, J. Algorithms43(2002), 190–200

work page 2002

[5] [5]

Borodin, On acyclic colorings of planar graphs,Discrete Math.25(1979), 211– 236

O.V. Borodin, On acyclic colorings of planar graphs,Discrete Math.25(1979), 211– 236

work page 1979

[6] [6]

Chappell and M.J

G.G. Chappell and M.J. Pelsmajer, Maximum induced forests in graphs of bounded treewidth,Electron. J. Combin.20, Article #P8

work page

[7] [7]

Dross, M

F. Dross, M. Montassier and A. Pinlou, Large induced forests in planar graphs with girth 4,Discrete Appl. Math.254(2019), 96–106

work page 2019

[8] [8]

Groenland, G

C. Groenland, G. Joret, W. Nadara and B. Walczak, Approximating pathwidth for graphs of small treewidth,ACM Trans. Algorithms19(2023), 1–19

work page 2023