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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1041,
author = {Piotr Borowiecki and Jaroslav Ivan\v co},
title = {P-bipartitions of minor hereditary properties},
journal = {Discussiones Mathematicae Graph Theory},
volume = {17},
year = {1997},
pages = {89-93},
zbl = {0914.05057},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1041}
}
Piotr Borowiecki; Jaroslav Ivančo. 𝓟-bipartitions of minor hereditary properties. Discussiones Mathematicae Graph Theory, Tome 17 (1997) pp. 89-93. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1041/
[000] [1] M. Borowiecki, I. Broere and P. Mihók, Minimal reducible bounds for planar graphs (submitted). | Zbl 0945.05022
[001] [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. | Zbl 0902.05026
[002] [3] M. Borowiecki and P. Mihók, Hereditary Properties of Graphs, in: Advances in Graph Theory (Vishwa Intern. Publications, 1991) 41-68.
[003] [4] P. Borowiecki, P-Bipartitions of Graphs, Vishwa Intern. J. Graph Theory 2 (1993) 109-116.
[004] [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.
[005] [6] G. Chartrand and L. Lesniak, Graphs and Digraphs (Second Edition, Wadsworth & Brooks/Cole, Monterey, 1986). | Zbl 0666.05001
[006] [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. | Zbl 0046.41001
[007] [8] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94, doi: 10.1016/0012-365X(91)90166-Y. | Zbl 0742.05041
[008] [9] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995). | Zbl 0971.05046
[009] [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.
[010] [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. | Zbl 0911.05043
[011] [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. | Zbl 0705.05016
[012] [13] J. Wang, On point-linear arboricity of planar graphs, Discrete Math. 72 (1988) 381-384, doi: 10.1016/0012-365X(88)90229-4. | Zbl 0665.05010