Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

The directed path partition conjecture

Marietjie FrickSusan van AardtGcina DlaminiJean DunbarOrtrud 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.

A path(ological) partition problem

Izak BroereMichael DorflingJean E. DunbarMarietjie 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.

Page 1

Download Results (CSV)