Open Research Index

Maximum Edge Open Packing in Permutation, Interval, and Well-Partitioned Chordal Graphs

Gautam K. Das, Kamal Santra

arXivarxiv/2608.05310Aug 5, 2026cs.DMscore 0

Edge open packing is a relaxation of induced matching in which the selected edges may induce disjoint stars. We study the \textsc{Maximum Edge Open Packing} problem on permutation graphs, interval graphs, and well-partitioned chordal graphs. For the first two classes, we introduce an oriented star-conflict graph whose vertices are ordered edges. We prove that its compatibility graph admits a natural transitive orientation: a product-order orientation for permutation graphs and a left-to-right orientation for interval graphs. In each case, a maximum edge open packing is obtained from a…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2608.05310
curl -X POST /api/v1/records/arxiv/2608.05310/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.05310/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'