Forbidden Triples Generating a Finite set of 3-Connected Graphs

  • Yoshimi Egawa
  • Jun Fujisawa
  • Michitaka Furuya
  • Michael D Plummer
  • Akira Saito
Keywords: Forbidden subgraph, Forbidden triple, $3$-connected graph


For a graph $G$ and a set $\mathcal{F}$ of connected graphs, $G$ is said be $\mathcal{F}$-free if $G$ does not contain any member of $\mathcal{F}$ as an induced subgraph. We let $\mathcal{G} _{3}(\mathcal{F})$ denote the set of all $3$-connected $\mathcal{F}$-free graphs. This paper is concerned with sets $\mathcal{F}$ of connected graphs such that $|\mathcal{F}|=3$ and $\mathcal{G} _{3}(\mathcal{F})$ is finite. Among other results, we show that for an integer $m\geq 3$ and a connected graph $T$ of order greater than or equal to $4$, $\mathcal{G} _{3}(\{K_{4},K_{2,m},T\})$ is finite if and only if $T$ is a path of order $4$ or $5$.

Article Number