Download PDF - A path(ological) partition problemAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

A path(ological) partition problem

Authors 1, 1, 2, 3

Affiliations

  1. Rand Afrikaans University, Auckland Park, 2006 South Africa
  2. Converse College, Spartanburg, SC 29302 USA
  3. 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

ENG
vertex partition, τ-partitionable, decomposable graph

Bibliography

  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. Šafárik University, Košice, 1986.
Discussiones Mathematicae Graph Theory
1998/18/1
Export to PBN, Opens in new tab
Pages:
113-125
Main language of publication
English
Received
1997-10-10
Accepted
1998-02-27
Published
1998

DOI: 10.7151/dmgt.1068

Exact and natural sciences