Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On Ramsey $(K_{1,2}, Kₙ)$-minimal graphs

100%

Hałuszczak M.

Discussiones Mathematicae Graph Theory

|

2012

|

tom 32

|

nr 2

331-339

EN

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 show how to receive infinite family of $(K_{1,2}, Kₙ)$-minimal graphs, for every n ≥ 3.

2

On the completeness of decomposable properties of graphs

64%

Hałuszczak M., Vateha P.

Discussiones Mathematicae Graph Theory

|

1999

|

tom 19

|

nr 2

229-236

EN

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 2.

3

Partitions of some planar graphs into two linear forests

64%

Borowiecki P., Hałuszczak M.

Discussiones Mathematicae Graph Theory

|

1997

|

tom 17

|

nr 1

95-102

EN

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 the graph G in the plane). We prove that there exists an (LF, LF)-partition for any plane graph G when certain conditions on the degree of the internal vertices and their neighbourhoods are satisfied.

4

Acyclic reducible bounds for outerplanar graphs

51%

Borowiecki M., Fiedorowicz A., Hałuszczak M.

Discussiones Mathematicae Graph Theory

|

2009

|

tom 29

|

nr 2

219-239

EN

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, then we say that R is an acyclic reducible bound for 𝓟. In this paper we present acyclic reducible bounds for the class of outerplanar graphs.

5

Preface

45%

Drgas-Burchardt E., Hałuszczak M., Kwaśnik M., Michalak D., Sidorowicz E.

Discussiones Mathematicae Graph Theory

|

2013

|

tom 33

|

nr 1

5-6

Ograniczanie wyników

5 Discussiones Mathematicae Graph Theory

5 Hałuszczak M.

1 Borowiecki M.

1 Borowiecki P.

1 Drgas-Burchardt E.

1 Fiedorowicz A.

1 Kwaśnik M.

1 Michalak D.

1 Sidorowicz E.

1 Vateha P.

1 2013

1 2012

1 2009

1 1999

1 1997

On Ramsey $(K_{1,2}, Kₙ)$-minimal graphs

On the completeness of decomposable properties of graphs

Partitions of some planar graphs into two linear forests

Acyclic reducible bounds for outerplanar graphs

Preface