DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory  18(1) (1998)   113-125
DOI: 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 k1 and k2 be positive integers such that τ(G) = k1 +k2. The question at hand is whether the vertex set V(G) can be partitioned into two subsets V1 and V2 such that τ(G[V1] ) ≤ k1 and τ(G[ V2] ) ≤ k2. 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