Factorizations and characterizations of induced‐hereditary and compositive properties

DOI10.1002/JGT.20062zbMATH Open1067.05057arXivmath/0308045OpenAlexW4236276689WikidataQ114236192 ScholiaQ114236192MaRDI QIDQ4680401FDOQ4680401

Authors: Alastair Farrugia, Peter Mihók, R. B. Richter, Gabriel Semanišin 

Publication date: 1 June 2005

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: A graph property (i.e., a set of graphs) is induced-hereditary or additive if it is closed under taking induced-subgraphs or disjoint unions. If $cP$ and $cQ$ are properties, the product $cPcirccQ$ consists of all graphs $G$ for which there is a partition of the vertex set of $G$ into (possibly empty) subsets $A$ and $B$ with $G[A]incP$ and $G[B]incQ$. A property is reducible if it is the product of two other properties, and irreducible otherwise. We completely describe the few reducible induced-hereditary properties that have a unique factorisation into irreducibles. Analogs of compositive and additive induced-hereditary properties are introduced and characterised in the style of Scheinerman [{em Discrete Math}. {�f 55} (1985) 185--193]. One of these provides an alternative proof that an additive hereditary property factors into irreducible additive hereditary properties.

Full work available at URL: https://arxiv.org/abs/math/0308045

Recommendations

• Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors
• Unique factorisation of additive induced-hereditary properties
• Unique factorization theorem
• Reducible properties of graphs
• On the factorization of reducible properties of graphs into irreducible factors

zbMATH Keywords

graph partitioninghereditaryreduciblegraph propertiesuniquecompositive

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Cites Work

• A survey of hereditary properties of graphs
• Unique factorisation of additive induced-hereditary properties
• Complexity of graph partition problems
• Generalized colorings and avoidable orientations
• Unique factorization theorem

Cited In (10)

• Unique factorisation of additive induced-hereditary properties
• Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors
• Unique factorization of compositive hereditary graph properties
• Prime ideals in the lattice of additive induced-hereditary graph properties
• On invariants of hereditary graph properties
• Unique Factorization Theorem and Formal Concept Analysis
• On generating sets of induced-hereditary properties
• Minimal forbidden subgraphs of reducible graph properties
• Unique factorization theorem
• On characterizations by nice forbidding sets

This page was built for publication: Factorizations and characterizations of induced‐hereditary and compositive properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4680401)