Forbidden Pairs with a Common Graph Generating Almost the Same Sets

Shuya Chiba, Jun Fujisawa, Michitaka Furuya, Hironobu Ikarashi


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 [Combin. Probab. Comput. 22 (2013) 733–748] concerning forbidden pairs.


Forbidden subgraph; Star-free graph; Vertex-transitive graph

Full Text: PDF