Forbidden pairs with a common graph generating almost the same sets (Q528989)

Summary: Let \(\mathcal{H}\) be a family of connected graphs. A graph \(G\) is said to be \(\mathcal{H}\)-free if \(G\) does not contain any members of \(\mathcal{H}\) as an induced subgraph. Let \(\mathcal{F}(\mathcal{H})\) be the family of connected \(\mathcal{H}\)-free graphs. In this context, the members of \(\mathcal{H}\) are called forbidden subgraphs.{ }In this paper, we focus on two pairs of forbidden subgraphs containing a common graph, and compare the classes of graphs satisfying each of the two forbidden subgraph conditions. Our main result is the following: Let \(H_{1}\), \(H_{2}\), \(H_{3}\) be connected graphs of order at least three, and suppose that \(H_{1}\) is twin-less. If the symmetric difference of \(\mathcal{F}(\{H_{1},H_{2}\})\) and \(\mathcal{F}(\{H_{1},H_{3}\})\) is finite and the tuple \((H_{1};H_{2},H_{3})\) is non-trivial in a sense, then \(H_{2}\) and \(H_{3}\) are obtained from the same vertex-transitive graph by successively replacing a vertex with a clique and joining the neighbors of the original vertex and the clique. Furthermore, we refine a result in [\textit{S. Fujita}, Comb. Probab. Comput. 22, No. 5, 733--748 (2013; Zbl 1282.05167)] concerning forbidden pairs.