{"id":"arxiv/2610.02275","url":"https://arxiv.org/abs/2610.02275","tags":["cs.DM","math.CO"],"score":0,"title":"Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs","domain":"cs.DM","source":"arxiv","authors":["Gautam K. Das","Kamal Santra"],"reviews":0,"subject":"cs.DM","summary":"An edge open packing is a set of edges whose endpoints induce a disjoint union of stars. We study the problem of finding a maximum edge open packing in AT-free, chordal, and convex bipartite graphs. For AT-free graphs, we use the oriented star-conflict graph $A_G$, introduced by Das and Santra, for which $ρ_e^o(G)=α(A_G)$, and prove that $A_G$ is AT-free whenever $G$ is AT-free. Consequently, a known maximum independent set algorithm for AT-free graphs yields an $O(n^2+m^4)$-time algorithm for Maximum Edge Open Packing, where $n$ and $m$ denote the numbers of vertices and edges of $G$,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}