A note on partial 3-trees and homomorphism bases of graphs
type: Item
instance of: scholarly article
title: A note on partial 3-trees and homomorphism bases of graphs
zbMATH Open document ID: 0823.05047
DOI: 10.1007/BF02941329
published in: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
publication date: 1994-02-06T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 492580
zbMATH Keywords: partial 3-trees
zbMATH Keywords: homomorphism bases
zbMATH Keywords: simplicial decomposition
zbMATH Keywords: simplicial attachments
zbMATH Keywords: prime graph decomposition
zbMATH Keywords: prime factors
zbMATH Keywords: closed under simplicial decomposition
zbMATH Keywords: minor
zbMATH Keywords: homomorphism base
zbMATH Keywords: exchange property
zbMATH Keywords: planar graphs
author: Rudolf Halin
reviewed by: Radim Jiroušek
MaRDI profile type: Publication
cites work: Forbidden minors characterization of partial 3-trees
cites work: Q3999150
cites work: Q3992521
cites work: Zur Klassifikation der endlichen Graphen nach H. Hadwiger und K. Wagner
cites work: S-functions for graphs
cites work: Über Minimalstrukturen von Graphen, insbesondere von n-fach zusammenhängenden Graphen
cites work: Q5528475
cites work: A characterization of partial 3-trees
cites work: Über eine Eigenschaft der ebenen Komplexe
cites work: Bemerkungen zu Hadwigers Vermutung
full work available at URL: https://doi.org/10.1007/bf02941329
OpenAlex ID: W2088986635
description: scientific article; zbMATH DE number 492580