Structural and Polynomial-Time Results on Core and Corona in Odd-Bicyclic Graphs

Let $\text{core}G$ and $\text{corona}G$ denote the intersection and the union, respectively, of all maximum independent sets of a graph $G$. In this work, we show that for a graph with at most two odd cycles, $\text{a}\text{core}G+\text{a}\text{corona}G$ is equal to $2\alpha (G)$, $2\alpha (G)+1$, or $2\alpha (G)+2$, and we precisely characterize when each value occurs. We further characterize graphs with at most two odd cycles that admit the core–corona partition $V(G)=\text{corona}G\text{ud}N(\text{core}G)$, extending known results for König–Egerváry and almost bipartite graphs. Deciding whether $\text{core}G=\mathrm{\varnothing }$ is known to be $\mathbf{\text{NP}}$-hard. As an algorithmic consequence of the obtained results, we show that the core, independence number and the corona can be computed in polynomial time for this class of graphs.