# A path(ological) partition problem

Izak Broere; Michael Dorfling; Jean E. Dunbar; Marietjie Frick

Discussiones Mathematicae Graph Theory (1998)

- Volume: 18, Issue: 1, page 113-125
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topIzak Broere, et al. "A path(ological) partition problem." Discussiones Mathematicae Graph Theory 18.1 (1998): 113-125. <http://eudml.org/doc/270308>.

@article{IzakBroere1998,

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.},

author = {Izak Broere, Michael Dorfling, Jean E. Dunbar, Marietjie Frick},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {vertex partition; τ-partitionable; decomposable graph; -partitionable; longest path},

language = {eng},

number = {1},

pages = {113-125},

title = {A path(ological) partition problem},

url = {http://eudml.org/doc/270308},

volume = {18},

year = {1998},

}

TY - JOUR

AU - Izak Broere

AU - Michael Dorfling

AU - Jean E. Dunbar

AU - Marietjie Frick

TI - A path(ological) partition problem

JO - Discussiones Mathematicae Graph Theory

PY - 1998

VL - 18

IS - 1

SP - 113

EP - 125

AB - 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.

LA - eng

KW - vertex partition; τ-partitionable; decomposable graph; -partitionable; longest path

UR - http://eudml.org/doc/270308

ER -

## References

top- [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. Zbl0902.05026
- [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. Zbl0902.05027
- [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. Zbl0906.05059
- [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. Zbl0173.26204
- [5] G. Chartrand and L. Lesniak, Graphs and Digraphs, second edition (Wadsworth & Brooks/Cole, Monterey, 1986). Zbl0666.05001
- [6] G. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69. Zbl0047.17001
- [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. Zbl0593.05041
- [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. Zbl0151.33401
- [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 Zbl0865.05058
- [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.

## Citations in EuDML Documents

top- Marietjie Frick, Susan van Aardt, Gcina Dlamini, Jean Dunbar, Ortrud Oellermann, The directed path partition conjecture
- Marietjie Frick, Frank Bullock, Detour chromatic numbers
- Michael J. Dorfling, Samantha Dorfling, Generalized edge-chromatic numbers and additive hereditary properties of graphs
- Izak Broere, Samantha Dorfling, Elizabeth Jonck, Generalized chromatic numbers and additive hereditary properties of graphs
- Marietjie Frick, A Survey of the Path Partition Conjecture

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.