𝓟-bipartitions of minor hereditary properties

Piotr Borowiecki; Jaroslav Ivančo

Discussiones Mathematicae Graph Theory (1997)

  • Volume: 17, Issue: 1, page 89-93
  • ISSN: 2083-5892

Abstract

top
We prove that for any two minor hereditary properties 𝓟₁ and 𝓟₂, such that 𝓟₂ covers 𝓟₁, and for any graph G ∈ 𝓟₂ there is a 𝓟₁-bipartition of G. Some remarks on minimal reducible bounds are also included.

How to cite

top

Piotr Borowiecki, and Jaroslav Ivančo. "𝓟-bipartitions of minor hereditary properties." Discussiones Mathematicae Graph Theory 17.1 (1997): 89-93. <http://eudml.org/doc/270763>.

@article{PiotrBorowiecki1997,
abstract = {We prove that for any two minor hereditary properties 𝓟₁ and 𝓟₂, such that 𝓟₂ covers 𝓟₁, and for any graph G ∈ 𝓟₂ there is a 𝓟₁-bipartition of G. Some remarks on minimal reducible bounds are also included.},
author = {Piotr Borowiecki, Jaroslav Ivančo},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {minor hereditary property of graphs; generalized colouring; bipartitions of graphs; bipartition; minor hereditary properties; forbidden minor},
language = {eng},
number = {1},
pages = {89-93},
title = {𝓟-bipartitions of minor hereditary properties},
url = {http://eudml.org/doc/270763},
volume = {17},
year = {1997},
}

TY - JOUR
AU - Piotr Borowiecki
AU - Jaroslav Ivančo
TI - 𝓟-bipartitions of minor hereditary properties
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 1
SP - 89
EP - 93
AB - We prove that for any two minor hereditary properties 𝓟₁ and 𝓟₂, such that 𝓟₂ covers 𝓟₁, and for any graph G ∈ 𝓟₂ there is a 𝓟₁-bipartition of G. Some remarks on minimal reducible bounds are also included.
LA - eng
KW - minor hereditary property of graphs; generalized colouring; bipartitions of graphs; bipartition; minor hereditary properties; forbidden minor
UR - http://eudml.org/doc/270763
ER -

References

top
  1. [1] M. Borowiecki, I. Broere and P. Mihók, Minimal reducible bounds for planar graphs (submitted). Zbl0945.05022
  2. [2] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanisin, A survey of hereditary properties of graphs, Discussiones Mathematicae Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. Zbl0902.05026
  3. [3] M. Borowiecki and P. Mihók, Hereditary Properties of Graphs, in: Advances in Graph Theory (Vishwa Intern. Publications, 1991) 41-68. 
  4. [4] P. Borowiecki, P-Bipartitions of Graphs, Vishwa Intern. J. Graph Theory 2 (1993) 109-116. 
  5. [5] I. Broere and C.M. Mynhardt, Generalized colourings of outerplanar and planar graphs, in: Graph Theory with Applications to Algorithms and Computer Science (Willey, New York, 1985) 151-161. 
  6. [6] G. Chartrand and L. Lesniak, Graphs and Digraphs (Second Edition, Wadsworth & Brooks/Cole, Monterey, 1986). Zbl0666.05001
  7. [7] G. Dirac, A property of 4-chromatic graphs and remarks on critical graphs, J. London Math. Soc. 27 (1952) 85-92, doi: 10.1112/jlms/s1-27.1.85. Zbl0046.41001
  8. [8] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94, doi: 10.1016/0012-365X(91)90166-Y. Zbl0742.05041
  9. [9] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
  10. [10] P. Mihók, On the vertex partition numbers of graphs, in: M. Fiedler, ed., Graphs and Other Combinatorial Topics, Proc. Third Czech. Symp. Graph Theory, Prague, 1982 (Teubner-Verlag, Leipzig, 1983) 183-188. 
  11. [11] P. Mihók, On the minimal reducible bound for outerplanar and planar graphs, Discrete Math. 150 (1996) 431-435, doi: 10.1016/0012-365X(95)00211-E. Zbl0911.05043
  12. [12] K.S. Poh, On the Linear Vertex-Arboricity of a Planar Graph, J. Graph Theory 14 (1990) 73-75, doi: 10.1002/jgt.3190140108. Zbl0705.05016
  13. [13] J. Wang, On point-linear arboricity of planar graphs, Discrete Math. 72 (1988) 381-384, doi: 10.1016/0012-365X(88)90229-4. Zbl0665.05010

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.