Download PDF - -bipartitions of minor hereditary propertiesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

-bipartitions of minor hereditary properties

Authors 1, 2

Affiliations

  1. Institute of Mathematics, Technical University
  2. Department of Geometry and Algebra, P.J. Šafárik University

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.

Keywords

ENG
minor hereditary property of graphs, generalized colouring, bipartitions of graphs

Bibliography

  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.
Discussiones Mathematicae Graph Theory
1997/17/1
Export to PBN, Opens in new tab
Pages:
89-93
Main language of publication
English
Received
1997-02-25
Published
1997
Exact and natural sciences