Graphs in which all maximal bipartite subgraphs have the same order (Q2216453)

If \(G\) is a graph, then \(G\) is called well-covered if every inclusion-wise maximal independent set of vertices is maximum. In other words, in such graphs every vertex lies in a largest independent set of vertices. This topic is a classical one and has been addressed by many researchers previously. In this paper, the authors consider a related concept. More precisely, they are defining a graph to be well-bicovered, if all vertex-maximal bipartite subgraphs of \(G\) have the same order. In the paper, the authors compare this notion with that of well-coveredness. The main conclusion of the authors is that the two notions are not related. In other words, neither of them implies the other one. Next, the authors characterize the graphs in which the size of all vertex-maximal bipartite subgraphs is 2, 3 or \(|V|-1\). Then, the authors study the notion from the perspective of graph operations. The main operations that are considered in the paper are the union, join, lexicographic and Cartesian products of graphs. Finally, in the end of the paper, the authors present a characterization of the maximal outerplanar well-bicovered graphs.