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

Abstract

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

How to cite

top

Izak 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. [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. [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. [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. [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. [5] G. Chartrand and L. Lesniak, Graphs and Digraphs, second edition (Wadsworth & Brooks/Cole, Monterey, 1986). Zbl0666.05001
  6. [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. [7] P. Hajnal, Graph partitions (in Hungarian), Thesis, supervised by L. Lovász, J.A. University, Szeged, 1984. 
  8. [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. [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. [10] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238. Zbl0151.33401
  11. [11] P. Mihók, Problem 4, p. 86 in: M. Borowiecki and Z. Skupień (eds), Graphs, Hypergraphs and Matroids (Zielona Góra, 1985). 
  12. [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. [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
  1. Marietjie Frick, Susan van Aardt, Gcina Dlamini, Jean Dunbar, Ortrud Oellermann, The directed path partition conjecture
  2. Marietjie Frick, Frank Bullock, Detour chromatic numbers
  3. Michael J. Dorfling, Samantha Dorfling, Generalized edge-chromatic numbers and additive hereditary properties of graphs
  4. Izak Broere, Samantha Dorfling, Elizabeth Jonck, Generalized chromatic numbers and additive hereditary properties of graphs
  5. Marietjie Frick, A Survey of the Path Partition Conjecture

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.