Currently displaying 1 – 17 of 17

Showing per page

Order by Relevance | Title | Year of publication

Universality for and in Induced-Hereditary Graph Properties

Izak Broere;  Johannes Heidema — 2013

Discussiones Mathematicae Graph Theory

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

Minimal reducible bounds for hom-properties of graphs

Amelie Berger;  Izak Broere — 1999

Discussiones Mathematicae Graph Theory

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.

Hamiltonicity and Generalised Total Colourings of Planar Graphs

Mieczysław Borowiecki;  Izak Broere — 2016

Discussiones Mathematicae Graph Theory

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

Universality in Graph Properties with Degree Restrictions

Izak Broere;  Johannes Heidema;  Peter Mihók — 2013

Discussiones Mathematicae Graph Theory

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

Maximal graphs with respect to hereditary properties

Izak Broere;  Marietjie Frick;  Gabriel Semanišin — 1997

Discussiones Mathematicae Graph Theory

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

On generalized list colourings of graphs

Mieczysław Borowiecki;  Izak Broere;  Peter Mihók — 1997

Discussiones Mathematicae Graph Theory

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 order of uniquely partitionable graphs

Izak Broere;  Marietjie Frick;  Peter Mihók — 1997

Discussiones Mathematicae Graph Theory

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 ₁,...,ₙ.

Generalized chromatic numbers and additive hereditary properties of graphs

Izak Broere;  Samantha Dorfling;  Elizabeth Jonck — 2002

Discussiones Mathematicae Graph Theory

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

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

Izak Broere;  Jozef Bucko;  Peter Mihók — 2002

Discussiones Mathematicae Graph Theory

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.

The decomposability of additive hereditary properties of graphs

Izak Broere;  Michael J. Dorfling — 2000

Discussiones Mathematicae Graph Theory

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 = ₁⊕ ₂....

Factorizations of properties of graphs

Izak Broere;  Samuel John Teboho Moagi;  Peter Mihók;  Roman Vasky — 1999

Discussiones Mathematicae Graph Theory

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 = ₁∘₂∘...∘ₙ;...

A survey of hereditary properties of graphs

Mieczysław Borowiecki;  Izak Broere;  Marietjie Frick;  Peter Mihók;  Gabriel Semanišin — 1997

Discussiones Mathematicae Graph Theory

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.

Note on partitions of planar graphs

Izak Broere;  Bonita S. Wilson;  Jozef Bucko — 2005

Discussiones Mathematicae Graph Theory

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.

A path(ological) partition problem

Izak Broere;  Michael Dorfling;  Jean E. Dunbar;  Marietjie Frick — 1998

Discussiones Mathematicae Graph Theory

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.

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

Izak Broere;  Moroli D.V. Matsoha;  Johannes Heidema — 2016

Discussiones Mathematicae Graph Theory

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

Page 1

Download Results (CSV)