ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory  17(1) (1997)   89-93
DOI: 10.7151/dmgt.1041


Piotr Borowiecki

Institute of Mathematics
Technical University
Podgórna 50, 65-246 Zielona Góra, Poland


Jaroslav Ivančo

Department of Geometry and Algebra
P.J. Šafárik University
Jesenná 5, 041 54 Košice, Slovakia



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

Keywords: minor hereditary property of graphs, generalized colouring, bipartitions of graphs.

1991 Mathematics Subject Classification: 05C70, 05C15.


[1] M. Borowiecki, I. Broere and P. Mihók, Minimal reducible bounds for planar graphs (submitted).
[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.
[3] M. Borowiecki and P. Mihók, Hereditary Properties of Graphs, in: Advances in Graph Theory (Vishwa Intern. Publications, 1991) 41-68.
[4] P. Borowiecki, P-Bipartitions of Graphs, Vishwa Intern. J. Graph Theory 2 (1993) 109-116.
[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] G. Chartrand and L. Lesniak, Graphs and Digraphs (Second Edition, Wadsworth & Brooks/Cole, Monterey, 1986).
[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.
[8] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94, doi: 10.1016/0012-365X(91)90166-Y.
[9] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995).
[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] 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.
[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.
[13] J. Wang, On point-linear arboricity of planar graphs, Discrete Math. 72 (1988) 381-384, doi: 10.1016/0012-365X(88)90229-4.