Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 17

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

Universality for and in Induced-Hereditary Graph Properties

100%
Broere I., Heidema J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
33-47
EN
The well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal graphs in I with prescribed attributes. Then we contrast universality for and universality in induced-hereditary properties of graphs and show that the overwhelming majority of induced-hereditary properties contain no universal graphs. This is made precise by showing that there are 2(2א0 ) properties in the lattice K ≤ of induced-hereditary properties of which only at most 2א0 contain universal graphs. In a final section we discuss the outlook on future work; in particular the question of characterizing those induced-hereditary properties for which there is a universal graph in the property.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The decomposability of additive hereditary properties of graphs

100%
Broere I., Dorfling M.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
281-291
EN
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If 𝓟₁,...,𝓟ₙ are properties of graphs, then a (𝓟₁,...,𝓟ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that $G[E_i]$, the subgraph of G induced by $E_i$, is in $𝓟_i$, for i = 1,...,n. We define 𝓟₁ ⊕...⊕ 𝓟ₙ as the property {G ∈ 𝓘: G has a (𝓟₁,...,𝓟ₙ)-decomposition}. A property 𝓟 is said to be decomposable if there exist non-trivial hereditary properties 𝓟₁ and 𝓟₂ such that 𝓟 = 𝓟₁⊕ 𝓟₂. We study the decomposability of the well-known properties of graphs 𝓘ₖ, 𝓞ₖ, 𝓦ₖ, 𝓣ₖ, 𝓢ₖ, 𝓓ₖ and $𝓞 ^{p}$.
3
Content available remote

Hereditarnia

100%
Broere I., Mihók P.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 1
7-7
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Minimal reducible bounds for hom-properties of graphs

100%
Berger A., Broere I.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
143-158
EN
Let H be a fixed finite graph and let → H be a hom-property, i.e. the set of all graphs admitting a homomorphism into H. We extend the definition of → H to include certain infinite graphs H and then describe the minimal reducible bounds for → H in the lattice of additive hereditary properties and in the lattice of hereditary properties.
5
Content available remote

Hamiltonicity and Generalised Total Colourings of Planar Graphs

100%
Borowiecki M., Broere I.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
243-257
EN
The total generalised colourings considered in this paper are colourings of graphs such that the vertices and edges of the graph which receive the same colour induce subgraphs from two prescribed hereditary graph properties while incident elements receive different colours. The associated total chromatic number is the least number of colours with which this is possible. We study such colourings for sets of planar graphs and determine, in particular, upper bounds for these chromatic numbers for proper colourings of the vertices while the monochromatic edge sets are allowed to be forests. We also prove that if an even planar triangulation has a Hamilton cycle H for which there is no cycle among the edges inside H, then such a graph needs at most four colours for a total colouring as described above. The paper is concluded with some conjectures and open problems.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A path(ological) partition problem

81%
Broere I., Dorfling M., Dunbar J., Frick M.
Discussiones Mathematicae Graph Theory
|
1998
|
tom 18
|
nr 1
113-125
EN
Let τ(G) denote the number of vertices in a longest path of the graph G and let k₁ and k₂ be positive integers such that τ(G) = k₁ + k₂. The question at hand is whether the vertex set V(G) can be partitioned into two subsets V₁ and V₂ such that τ(G[V₁] ) ≤ k₁ and τ(G[V₂] ) ≤ k₂. We show that several classes of graphs have this partition property.
7
Content available remote

Universality in Graph Properties with Degree Restrictions

81%
Broere I., Heidema J., Mihók P.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
477-492
EN
Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: For given m and n with m < n, m is adjacent to n if n has a 1 in the m’th position of its binary expansion. It is well known that R is a universal graph in the set [...] of all countable graphs (since every graph in [...] is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of [...] is provided. We then construct a k-degenerate graph which is universal for the induced-hereditary property of finite k-degenerate graphs. In order to attempt the corresponding problem for the property of countable graphs with colouring number at most k + 1, the notion of a property with assignment is introduced and studied. Using this notion, we are able to construct a universal graph in this graph property and investigate its attributes.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Criteria for of the existence of uniquely partitionable graphs with respect to additive induced-hereditary properties

81%
Broere I., Bucko J., Mihók P.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
31-37
EN
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}.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Partition problems and kernels of graphs

81%
Broere I., Hajnal P., Mihók P.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 2
311-313
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On generalized list colourings of graphs

81%
Borowiecki M., Broere I., Mihók P.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
127-132
EN
Vizing [15] and Erdős et al. [8] independently introduce the idea of considering list-colouring and k-choosability. In the both papers the choosability version of Brooks' theorem [4] was proved but the choosability version of Gallai's theorem [9] was proved independently by Thomassen [14] and by Kostochka et al. [11]. In [3] some extensions of these two basic theorems to (𝓟,k)-choosability have been proved. In this paper we prove some extensions of the well-known bounds for the 𝓟-chromatic number to the (𝓟,k)-choice number and then an extension of Brooks' theorem.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The order of uniquely partitionable graphs

81%
Broere I., Frick M., Mihók P.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
115-125
EN
Let 𝓟₁,...,𝓟ₙ be properties of graphs. A (𝓟₁,...,𝓟ₙ)-partition of a graph G is a partition {V₁,...,Vₙ} of V(G) such that, for each i = 1,...,n, the subgraph of G induced by $V_i$ has property $𝓟_i$. If a graph G has a unique (𝓟₁,...,𝓟ₙ)-partition we say it is uniquely (𝓟₁,...,𝓟ₙ)-partitionable. We establish best lower bounds for the order of uniquely (𝓟₁,...,𝓟ₙ)-partitionable graphs, for various choices of 𝓟₁,...,𝓟ₙ.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Maximal graphs with respect to hereditary properties

81%
Broere I., Frick M., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
51-66
EN
A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by V_i has property $P_i$; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P is a hereditary property, then a graph G is called P- maximal if G has property P but G+e does not have property P for every e ∈ E([G̅]). We present some general results on maximal graphs and also investigate P-maximal graphs for various specific choices of P, including reducible hereditary properties.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Generalized chromatic numbers and additive hereditary properties of graphs

81%
Broere I., Dorfling S., Jonck E.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
259-270
EN
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let 𝓟 and 𝓠 be additive hereditary properties of graphs. The generalized chromatic number $χ_{𝓠}(𝓟)$ is defined as follows: $χ_{𝓠}(𝓟) = n$ iff 𝓟 ⊆ 𝓠 ⁿ but $𝓟 ⊊ 𝓠^{n-1}$. We investigate the generalized chromatic numbers of the well-known properties of graphs 𝓘ₖ, 𝓞ₖ, 𝓦ₖ, 𝓢ₖ and 𝓓ₖ.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Factorizations of properties of graphs

81%
Broere I., Teboho Moagi S., Mihók P., Vasky R.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
167-174
EN
A property of graphs is any isomorphism closed class of simple graphs. For given properties of graphs 𝓟₁,𝓟₂,...,𝓟ₙ a vertex (𝓟₁, 𝓟₂, ...,𝓟ₙ)-partition of a graph G is a partition {V₁,V₂,...,Vₙ} of V(G) such that for each i = 1,2,...,n the induced subgraph $G[V_i]$ has property $𝓟_i$. The class of all graphs having a vertex (𝓟₁, 𝓟₂, ...,𝓟ₙ)-partition is denoted by 𝓟₁∘𝓟₂∘...∘𝓟ₙ. A property 𝓡 is said to be reducible with respect to a lattice of properties of graphs 𝕃 if there are n ≥ 2 properties 𝓟₁,𝓟₂,...,𝓟ₙ ∈ 𝕃 such that 𝓡 = 𝓟₁∘𝓟₂∘...∘𝓟ₙ; otherwise 𝓡 is irreducible in 𝕃. We study the structure of different lattices of properties of graphs and we prove that in these lattices every reducible property of graphs has a finite factorization into irreducible properties.
15
Content available remote

The Quest for A Characterization of Hom-Properties of Finite Character

81%
Broere I., Matsoha M. D. V., Heidema J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
479-500
EN
A graph property is a set of (countable) graphs. A homomorphism from a graph G to a graph H is an edge-preserving map from the vertex set of G into the vertex set of H; if such a map exists, we write G → H. Given any graph H, the hom-property →H is the set of H-colourable graphs, i.e., the set of all graphs G satisfying G → H. A graph property P is of finite character if, whenever we have that F ∈ P for every finite induced subgraph F of a graph G, then we have that G ∈ P too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on H for →H to be of finite character. A notable (but known) sufficient condition is that H is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those H for which →H is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Note on partitions of planar graphs

81%
Broere I., Wilson B., Bucko J.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
211-215
EN
Chartrand and Kronk in 1969 showed that there are planar graphs whose vertices cannot be partitioned into two parts inducing acyclic subgraphs. In this note we show that the same is true even in the case when one of the partition classes is required to be triangle-free only.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A survey of hereditary properties of graphs

71%
Borowiecki M., Broere I., Frick M., Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
5-50
EN
In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
first rewind previous Strona / 1 next fast forward last
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ć.