𝓟-bipartitions of minor hereditary properties

• Autorzy: Piotr Borowiecki , Jaroslav Ivančo
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

minor hereditary property of graphs; generalized colouring; bipartitions of graphs

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1997
• Tom: 17
• Numer: 1
• Strony: 89-93

Daty

wydano

1997

otrzymano

1997-02-25

Twórcy

autor

Piotr Borowiecki

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

autor

Jaroslav Ivančo

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

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1041