Menu
For two graphs \( H \) and \( G \), a decomposition \( \mathcal{D} = \{H_1, H_2, \ldots, H_k, R\} \) of \( G \) is called an \( H \)-maximal \( k \)-decomposition if \( H_i \cong H \) for \( 1 \leq i \leq k \) and \( R \) contains no subgraph isomorphic to \( H \). Let \(\text{Min}(G, H)\) and \(\text{Max}(G, H)\) be the minimum and maximum \( k \), respectively, for which \( G \) has an \( H \)-maximal \( k \)-decomposition. A graph \( G \) without isolated vertices is said to possess the intermediate decomposition property if for each connected graph \( G \) and each integer \( k \) with \(\text{Min}(G, H) \leq k \leq \text{Max}(G, H)\), there exists an \( H \)-maximal \( k \)-decomposition of \( G \). For a set \( S \) of graphs and a graph \( G \), a decomposition \( \mathcal{D} = \{H_1, H_2, \ldots, H_k, R\} \) of \( G \) is called an \( S \)-maximal \( k \)-decomposition if \( H_i \cong H \) for some \( H \in S \) for each integer \( i \) with \( 1 \leq i \leq k \) and \( R \) contains no subgraph isomorphic to any subgraph in \( S \). Let \(\text{Min}(G, S)\) and \(\text{Max}(G, S)\) be the minimum and maximum \( k \), respectively, for which \( G \) has an \( S \)-maximal \( k \)-decomposition. A set \( S \) of graphs without isolated vertices is said to possess the intermediate decomposition property if for every connected graph \( G \) and each integer \( k \) with \(\text{Min}(G, S) \leq k \leq \text{Max}(G, S)\), there exists an \( S \)-maximal \( k \)-decomposition of \( G \). While all those graphs of size \( 3 \) have been determined that possess the intermediate decomposition property, as have all sets consisting of two such graphs, here all remaining sets of graphs having size \( 3 \) that possess the intermediate decomposition property are determined.