Pith. sign in

REVIEW 3 cited by

Forest Cuts in Sparse Graphs

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2409.17724 v1 pith:6BL5T54K submitted 2024-09-26 math.CO

Vsevolod Chernyshev , Johannes Rauch , Dieter Rautenbach This is my paper · ORCID
classification math.CO
keywords forestgraphsvertexconjecturecutsedgeseveryfrac
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We propose the conjecture that every graph $G$ of order $n$ with less than $3n-6$ edges has a vertex cut that induces a forest. Maximal planar graphs do not have such vertex cuts and show that the density condition would be best possible. We verify the conjecture for planar graphs and show that every graph $G$ of order $n$ with less than $\frac{11}{5}n-\frac{18}{5}$ edges has a vertex cut that induces a forest.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Sparse graphs with an independent or foresty minimum vertex cut

    math.CO 2024-12 accept novelty 7.0 of 10

    Every connected graph with n≥7 vertices and at most floor(3n/2) edges has an independent minimum vertex cut; every connected graph with n≥7 and at most 2n edges has a foresty minimum vertex cut; both bounds are sharp.

  2. The minimum size of a $k$-connected locally nonforesty graph

    math.CO 2025-01 conditional novelty 6.0 of 10

    The minimum size of a k-connected locally nonforesty graph of order n is determined exactly for k=4, k=2 and k=1, and equals ceil(kn/2) for k at least 5.

  3. Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs

    math.CO 2024-11 conditional novelty 6.0 of 10

    Connected graphs with fewer than 9/4 n - 15/4 edges always have a vertex cut inducing a forest, improving on the previous 11/5 n - 18/5 bound toward the conjectured 3n - 6.

Pith tools