DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

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

PDF

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

P-BIPARTITIONS OF MINOR HEREDITARY PROPERTIES

Piotr Borowiecki

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

e-mail: p.borowiecki@im.uz.zgora.pl

Jaroslav Ivančo

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

e-mail: ivanco@duro.upjs.sk

Abstract

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.

References

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