Currently displaying 1 – 5 of 5

Showing per page

Order by Relevance | Title | Year of publication

On Ramsey ( K 1 , 2 , K ₙ ) -minimal graphs

Mariusz Hałuszczak — 2012

Discussiones Mathematicae Graph Theory

Let F be a graph and let , denote nonempty families of graphs. We write F → (,) if in any 2-coloring of edges of F with red and blue, there is a red subgraph isomorphic to some graph from G or a blue subgraph isomorphic to some graph from H. The graph F without isolated vertices is said to be a (,)-minimal graph if F → (,) and F - e not → (,) for every e ∈ E(F). We present a technique which allows to generate infinite family of (,)-minimal graphs if we know some special graphs. In particular, we...

On the completeness of decomposable properties of graphs

Mariusz Hałuszczak;  Pavol Vateha — 1999

Discussiones Mathematicae Graph Theory

Let ₁,₂ be additive hereditary properties of graphs. A (₁,₂)-decomposition of a graph G is a partition of E(G) into sets E₁, E₂ such that induced subgraph G [ E i ] has the property i , i = 1,2. Let us define a property ₁⊕₂ by G: G has a (₁,₂)-decomposition. A property D is said to be decomposable if there exists nontrivial additive hereditary properties ₁, ₂ such that D = ₁⊕₂. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness...

Partitions of some planar graphs into two linear forests

Piotr Borowiecki;  Mariusz Hałuszczak — 1997

Discussiones Mathematicae Graph Theory

A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs ⟨V₁⟩ and ⟨V₂⟩ are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of...

Acyclic reducible bounds for outerplanar graphs

Mieczysław Borowiecki;  Anna Fiedorowicz;  Mariusz Hałuszczak — 2009

Discussiones Mathematicae Graph Theory

For a given graph G and a sequence ₁, ₂,..., ₙ of additive hereditary classes of graphs we define an acyclic (₁, ₂,...,Pₙ)-colouring of G as a partition (V₁, V₂,...,Vₙ) of the set V(G) of vertices which satisfies the following two conditions: 1. G [ V i ] ∈ i for i = 1,...,n, 2. for every pair i,j of distinct colours the subgraph induced in G by the set of edges uv such that u ∈ V i and v ∈ V j is acyclic. A class R = ₁ ⊙ ₂ ⊙ ... ⊙ ₙ is defined as the set of the graphs having an acyclic (₁, ₂,...,Pₙ)-colouring. If ⊆ R,...

Page 1

Download Results (CSV)