Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: An asymptotic Result for the Path Partition Conjecture. | An asymptotic Result for the Path Partition Conjecture Marietjie Frick University of South Africa PO. Box 392 UNISA 0003 South Africa Ingo Schiermeyery Technische Universitat Bergakademie Freiberg 09596 Freiberg Germany Submitted Apr 14 2004 Accepted Sep 1 2005 Published Sep 29 2005 Abstract The detour order of a graph G denoted by T G is the order of a longest path in G. A partition of the vertex set of G into two sets A and B such that T A a and T B b is called an a b -partition of G. If G has an a b -partition for every pair a b of positive integers such that a b T G then we say that G is T-partitionable. The Path Partition Conjecture PPC which was discussed by Lovasz and Mihók in 1981 in Szeged is that every graph is T-partitionable. It is known that a graph G of order n and detour order T n p is T-partitionable if p 0 1. We show that this is also true for p 2 3 and for all p 4 provided that n p 10p 3 . 1 Introduction The vertex set and edge set of a graph G is denoted by V G and E G respectively. The degree of a vertex v in G will be denoted by dG v . If H is a subgraph of G the open H-neighbourhood of v is the set NH v u 2 V H v I uv 2 E G g . If S is a subset of V G we write NH S S NH v . The subgraph of G induced by S is denoted v2S by S . A longest path in a graph G is called a detour of G. The number of vertices in a detour of G is called the detour order of G and denoted by T G . The number of vertices in a longest cycle of G is called the circumference of G and denoted by c G . A graph This material is based upon work supported by the National Research Foundation under Grant number 2053752. tPart of this research was done while the author was on sabbatical visiting UNISA. Financial support by UNISA is gratefully acknowledged. THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R48 1 of order n will be called hamiltonian or traceable if c G n or T G n respectively. The vertex independence number of a graph G is denoted by a G . A partition of the vertex set
