PDF

Discussiones Mathematicae Graph Theory  18(1) (1998)   113-125
DOI: https://doi.org/10.7151/dmgt.1068

A PATH(OLOGICAL) PARTITION PROBLEM

Izak Broere Michael Dorfling Rand Afrikaans University Auckland Park, 2006 South Africa

Jean E. Dunbar Converse College Spartanburg, SC 29302 USA

Marietjie Frick University of South Africa Pretoria, 0001 South Africa

Abstract

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.

Keywords: vertex partition, τ-partitionable, decomposable graph.

1991 Mathematics Subject Classification: 05C38.

References

[1]	M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discussiones Mathematicae Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
[2]	I. Broere, M. Frick and G. Semanišin, Maximal graphs with respect to hereditary properties, Discussiones Mathematicae Graph Theory 17 (1997) 51-66, doi: 10.7151/dmgt.1038.
[3]	I. Broere, P. Hajnal and P. Mihók, Partition problems and kernels of graph, Discussiones Mathematicae Graph Theory 17 (1997) 311-313, doi: 10.7151/dmgt.1058.
[4]	G. Chartrand, D.P. Geller and S.T. Hedetniemi, A generalization of the chromatic number, Proc. Camb. Phil. Soc. 64 (1968) 265-271, doi: 10.1017/S0305004100042808.
[5]	G. Chartrand and L. Lesniak, Graphs and Digraphs, second edition (Wadsworth & Brooks/Cole, Monterey, 1986).
[6]	G. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69.
[7]	P. Hajnal, Graph partitions (in Hungarian), Thesis, supervised by L. Lovász, J.A. University, Szeged, 1984.
[8]	L. Kászonyi and Zs. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory 10 (1986) 203-210, doi: 10.1002/jgt.3190100209.
[9]	J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982), 173-177 (Teubner-Texte Math., 59, 1983).
[10]	L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238.
[11]	P. Mihók, Problem 4, p. 86 in: M. Borowiecki and Z. Skupień (eds), Graphs, Hypergraphs and Matroids (Zielona Góra, 1985).
[12]	M. Stiebitz, Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321-324, doi: 10.1002/(SICI)1097-0118(199611)23:3<321::AID-JGT12>3.0.CO;2-H.
[13]	J. Vronka, Vertex sets of graphs with prescribed properties (in Slovak), Thesis, supervised by P. Mihók, P.J. Safárik University, Košice, 1986.

Received 10 October 1997
Revised 27 February 1998