Geodesic
A path(ological) partition problem
Discussiones Mathematicae. Graph Theory, Tome 18 (1998) no. 1, pp. 113-125.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_1998_18_1_a9,
     author = {Broere, Izak and Dorfling, Michael and Dunbar, Jean and Frick, Marietjie},
     title = {A path(ological) partition problem},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {113--125},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {1998},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1998_18_1_a9/}
}
TY  - JOUR
AU  - Broere, Izak
AU  - Dorfling, Michael
AU  - Dunbar, Jean
AU  - Frick, Marietjie
TI  - A path(ological) partition problem
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1998
SP  - 113
EP  - 125
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_1998_18_1_a9/
LA  - en
ID  - DMGT_1998_18_1_a9
ER  - 
%0 Journal Article
%A Broere, Izak
%A Dorfling, Michael
%A Dunbar, Jean
%A Frick, Marietjie
%T A path(ological) partition problem
%J Discussiones Mathematicae. Graph Theory
%D 1998
%P 113-125
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_1998_18_1_a9/
%G en
%F DMGT_1998_18_1_a9
Broere, Izak; Dorfling, Michael; Dunbar, Jean; Frick, Marietjie. A path(ological) partition problem. Discussiones Mathematicae. Graph Theory, Tome 18 (1998) no. 1, pp. 113-125. http://geodesic.mathdoc.fr/item/DMGT_1998_18_1_a9/

[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:3321::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.