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 𝓟₁,𝓟₂,...,𝓟ₙ be graph properties, a graph G is said to be uniquely (𝓟₁,𝓟₂, ...,𝓟ₙ)-partitionable if there is exactly one (unordered) partition {V₁,V₂,...,Vₙ} of V(G) such that $G[V_i] ∈ 𝓟_i$ for i = 1,2,...,n. We prove that for additive and induced-hereditary properties uniquely (𝓟₁,𝓟₂,...,𝓟ₙ)-partitionable graphs exist if and only if $𝓟_i$ and $𝓟_j$ are either coprime or equal irreducible properties of graphs for every i ≠ j, i,j ∈ {1,2,...,n}.
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.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
A graph property is any nonempty isomorphism-closed class of simple (finite or infinite) graphs. A graph property 𝓟 is of finite character if a graph G has a property 𝓟 if and only if every finite induced subgraph of G has a property 𝓟. Let 𝓟₁,𝓟₂,...,𝓟ₙ be graph properties of finite character, a graph G is said to be (uniquely) (𝓟₁, 𝓟₂, ...,𝓟ₙ)-partitionable if there is an (exactly one) partition {V₁, V₂, ..., Vₙ} of V(G) such that $G[V_i] ∈ 𝓟_i$ for i = 1,2,...,n. Let us denote by ℜ = 𝓟₁ ∘ 𝓟₂ ∘ ... ∘ 𝓟ₙ the class of all (𝓟₁,𝓟₂,...,𝓟ₙ)-partitionable graphs. A property ℜ = 𝓟₁ ∘ 𝓟₂ ∘ ... ∘ 𝓟ₙ, n ≥ 2 is said to be reducible. We prove that any reducible additive graph property ℜ of finite character has a uniquely (𝓟₁, 𝓟₂, ...,𝓟ₙ)-partitionable countable generating graph. We also prove that for a reducible additive hereditary graph property ℜ of finite character there exists a weakly universal countable graph if and only if each property $𝓟_i$ has a weakly universal graph.
An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let $L^a$ denote a class of all such properties. In the paper, we consider H-reducible over $L^a$ properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.
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ć.