Currently displaying 1 – 15 of 15

Showing per page

Order by Relevance | Title | Year of publication

A Survey of the Path Partition Conjecture

Marietjie Frick — 2013

Discussiones Mathematicae Graph Theory

The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.

Detour chromatic numbers

Marietjie Frick;  Frank Bullock — 2001

Discussiones Mathematicae Graph Theory

The nth detour chromatic number, χₙ(G) of a graph G is the minimum number of colours required to colour the vertices of G such that no path with more than n vertices is monocoloured. The number of vertices in a longest path of G is denoted by τ( G). We conjecture that χₙ(G) ≤ ⎡(τ(G))/n⎤ for every graph G and every n ≥ 1 and we prove results that support the conjecture. We also present some sufficient conditions for a graph to have nth chromatic number at most 2.

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

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

Self-diclique circulant digraphs

Marietjie Frick;  Bernardo Llano;  Rita Zuazua — 2015

Mathematica Bohemica

We study a particular digraph dynamical system, the so called digraph diclique operator. Dicliques have frequently appeared in the literature the last years in connection with the construction and analysis of different types of networks, for instance biochemical, neural, ecological, sociological and computer networks among others. Let D = ( V , A ) be a reflexive digraph (or network). Consider X and Y (not necessarily disjoint) nonempty subsets of vertices (or nodes) of D . A disimplex K ( X , Y ) of D is the subdigraph...

Independent Detour Transversals in 3-Deficient Digraphs

Susan van Aardt;  Marietjie Frick;  Joy Singleton — 2013

Discussiones Mathematicae Graph Theory

In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph is p-deficient...

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

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.

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 directed path partition conjecture

Marietjie Frick;  Susan van Aardt;  Gcina Dlamini;  Jean Dunbar;  Ortrud Oellermann — 2005

Discussiones Mathematicae Graph Theory

The Directed Path Partition Conjecture is the following: If D is a digraph that contains no path with more than λ vertices then, for every pair (a,b) of positive integers with λ = a+b, there exists a vertex partition (A,B) of D such that no path in D⟨A⟩ has more than a vertices and no path in D⟨B⟩ has more than b vertices. We develop methods for finding the desired partitions for various classes of digraphs.

Page 1

Download Results (CSV)