A hereditary property R of graphs is said to be reducible if there exist hereditary properties P₁,P₂ such that G ∈ R if and only if the set of vertices of G can be partitioned into V(G) = V₁∪V₂ so that ⟨V₁⟩ ∈ P₁ and ⟨V₂⟩ ∈ P₂. The problem of the factorization of reducible properties into irreducible factors is investigated.
Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that $⟨V₁⟩_G ∈ P₁$ and $⟨V₂⟩_G ∈ P₂$. The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.
Let 𝓟₁,...,𝓟ₙ be properties of graphs. A (𝓟₁,...,𝓟ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph $G[V_i]$ induced by $V_i$ has property $𝓟_i$; i = 1,...,n. A graph G is said to be uniquely (𝓟₁, ...,𝓟ₙ)-partitionable if G has exactly one (𝓟₁,...,𝓟ₙ)-partition. A property 𝓟 is called hereditary if every subgraph of every graph with property 𝓟 also has property 𝓟. If every graph that is a disjoint union of two graphs that have property 𝓟 also has property 𝓟, then we say that 𝓟 is additive. A property 𝓟 is called degenerate if there exists a bipartite graph that does not have property 𝓟. In this paper, we prove that if 𝓟₁,..., 𝓟ₙ are degenerate, additive, hereditary properties of graphs, then there exists a uniquely (𝓟₁,...,𝓟ₙ)-partitionable graph.
In this paper we translate Ramsey-type problems into the language of decomposable hereditary properties of graphs. We prove a distributive law for reducible and decomposable properties of graphs. Using it we establish some values of graph theoretical invariants of decomposable properties and show their correspondence to generalized Ramsey numbers.
A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique Factorization Theorem for induced-hereditary properties of graphs.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.