Currently displaying 1 – 7 of 7

Showing per page

Order by Relevance | Title | Year of publication

Uniquely partitionable planar graphs with respect to properties having a forbidden tree

Jozef Bucko;  Jaroslav Ivančo — 1999

Discussiones Mathematicae Graph Theory

Let ₁, ₂ be graph properties. A vertex (₁,₂)-partition of a graph G is a partition V₁,V₂ of V(G) such that for i = 1,2 the induced subgraph G [ V i ] has the property i . A property ℜ = ₁∘₂ is defined to be the set of all graphs having a vertex (₁,₂)-partition. A graph G ∈ ₁∘₂ is said to be uniquely (₁,₂)-partitionable if G has exactly one vertex (₁,₂)-partition. In this note, we show the existence of uniquely partitionable planar graphs with respect to hereditary additive properties having a forbidden tree....

On uniquely partitionable relational structures and object systems

Jozef Bucko;  Peter Mihók — 2006

Discussiones Mathematicae Graph Theory

We introduce object systems as a common generalization of graphs, hypergraphs, digraphs and relational structures. Let C be a concrete category, a simple object system over C is an ordered pair S = (V,E), where E = A₁,A₂,...,Aₘ is a finite set of the objects of C, such that the ground-set V ( A i ) of each object A i ∈ E is a finite set with at least two elements and V ⊇ ⋃ i = 1 m V ( A i ) . To generalize the results on graph colourings to simple object systems we define, analogously as for graphs, that an additive induced-hereditary...

On infinite uniquely partitionable graphs and graph properties of finite character

Jozef Bucko;  Peter Mihók — 2009

Discussiones Mathematicae Graph Theory

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

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.

Uniquely partitionable graphs

Jozef Bucko;  Marietjie Frick;  Peter Mihók;  Roman Vasky — 1997

Discussiones Mathematicae Graph Theory

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

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 note on maximal common subgraphs of the Dirac's family of graphs

Jozef Bucko;  Peter Mihók;  Jean-François Saclé;  Mariusz Woźniak — 2005

Discussiones Mathematicae Graph Theory

Let ⁿ be a given set of unlabeled simple graphs of order n. A maximal common subgraph of the graphs of the set ⁿ is a common subgraph F of order n of each member of ⁿ, that is not properly contained in any larger common subgraph of each member of ⁿ. By well-known Dirac’s Theorem, the Dirac’s family ⁿ of the graphs of order n and minimum degree δ ≥ [n/2] has a maximal common subgraph containing Cₙ. In this note we study the problem of determining all maximal common subgraphs of the Dirac’s family...

Page 1

Download Results (CSV)