A note on partial 3-trees and homomorphism bases of graphs (Q1313444)

The paper deals with characterization of sets of finite graphs by their homomorphism bases. The primary notion is that of a simplicial decomposition of a graph \(G\) which is defined to be a sequence \(G_ 1,\dots, G_ k\) of subgraphs of \(G\) such that \(G= G_ 1\cup\cdots\cup G_ k\), and for all \(j= 2,\dots, k\), \[ G_ j\cap\Biggl( \bigcup^{j- 1}_{\ell= 1} G_ \ell\Biggr) \] are complete graphs (so-called simplicial attachments). If the simplicial decomposition is such that no \(G_ j\) has its own proper simplicial decomposition (i.e., all these subgraphs are prime) then the decomposition is called prime graph decomposition and all its elements are prime factors of \(G\). A class \(\Gamma\) of graphs is closed under simplicial decomposition if \(G\in \Gamma\) just in case \(\Gamma\) contains all prime factors of \(G\). For a class \(\Phi\) of graphs, \(H(\Phi)\) denotes the set of all graphs not having elements of \(\Phi\) as a minor; \(\widehat H(\Phi)\) is the subclass of maximal graphs in \(H(\Phi)\). \(\Phi\) is regular if \(H(\Phi)\) is closed under simplicial decomposition. The homomorphism base \(B(\Phi)\) of \(\Phi\) is the class of all prime graphs which occur in a prime graph decomposition of any element of \(\widehat H(\Phi)\). The main result of the paper is the so-called exchange property saying that \(B(\Phi\cup \Psi)= B(\Phi)\backslash \Psi\) holds if \(\Phi\) is a regular class of 4-connected graphs and \(\Psi= \{G\in B(\Phi): G\neq K_ 4\}\). Moreover, the author proves that \(\Phi\cup \Psi\) is again regular. The paper concludes by presenting some new homomorphism bases; the author characterizes the planar graphs which do not have \(K_{2,2,2}\) as a minor.