On uniqueness of a general factorization of graph properties

✍ Scribed by Ewa Drgas-Burchardt

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 201 KB
• Volume: 62
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20409

✦ Synopsis

Abstract

A graph property is any class of simple graphs, which is closed under isomorphisms. Let H be a given graph on vertices v~1~, …, v~n~. For graph properties
𝒫~1~, …, 𝒫~n~, we denote by H[𝒫~1~, …, 𝒫~n~] the class of those (𝒫~1~, …, 𝒫~n~) ‐partitionable graphs G, with a corresponding vertex partition (V~1~, …, V~n~), for which an edge {x~i~, x~j~} with x~i~∈V~i~ and x~j~∈V~j~ implies the existence of the edge {v~i~, v~j~} in the graph H. The problem of the unique description of a graph property 𝒫 in the form H[𝒫~1~, …, 𝒫~n~] is investigated for 𝒫, 𝒫~1~, …, 𝒫~n~ being from the class L^a^ of all graph properties closed under taking disjoint unions and subgraphs. The unique factorization theorems obtained in the paper generalize known results of this type bringing together ∘ ‐reducibility over L^a^ and ∨ ‐reducibility in the lattice (L^a^, ⊆). There is also offered a new insight into the modular decomposition tree for a graph. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 48–64, 2009