{"id":"arxiv/2608.05310","url":"https://arxiv.org/abs/2608.05310","tags":["cs.DM","math.CO"],"score":0,"title":"Maximum Edge Open Packing in Permutation, Interval, and Well-Partitioned Chordal Graphs","domain":"cs.DM","source":"arxiv","authors":["Gautam K. Das","Kamal Santra"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-05","reactions":{}}