A note on Matching-Cut in $P_t$-free Graphs

Carl Feghali

REVIEW

A note on Matching-Cut in $P_t$-free 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 2111.12011 v3 pith:UJIKKJLW submitted 2021-11-23 math.CO cs.DMcs.DS

Carl Feghali This is my paper · ORCID

classification math.COcs.DMcs.DS

keywords matching-cutgraphsfreegraphnp-completebelongsclassesedge

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

abstract

A matching-cut of a graph is an edge cut that is a matching. The problem Matching-Cut is that of recognizing graphs with a matching-cut and is NP-complete, even if the graph belongs to one of a number of classes. We initiate the study of Matching-Cut for graphs without a fixed path as an induced subgraph. We show that Matching-Cut is in P for $P_5$-free graphs, but that there exists an integer $t > 0$ for which it is NP-complete for $P_{t}$-free graphs.

Discussion (0). Continue with ORCID to comment.

Pith tools