On the factorization of reducible properties of graphs into irreducible factors

• Autorzy: P. Mihók , R. Vasky
• Języki publikacji: EN

Abstrakty

EN

A hereditary property R of graphs is said to be reducible if there exist hereditary properties P₁,P₂ such that G ∈ R if and only if the set of vertices of G can be partitioned into V(G) = V₁∪V₂ so that ⟨V₁⟩ ∈ P₁ and ⟨V₂⟩ ∈ P₂. The problem of the factorization of reducible properties into irreducible factors is investigated.

Słowa kluczowe

EN

hereditary property of graphs; additivity; reducibility; vertex partition

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1995
• Tom: 15
• Numer: 2
• Strony: 195-203

Daty

wydano

1995

otrzymano

1995-05-10

Twórcy

autor

P. Mihók

• Department of Geometry and Algebra, Faculty of Sciences, P. J. Šafárik's University, Jesenná 5, 04154 Košice, Slovak Republic

autor

R. Vasky

• Department of Geometry and Algebra, Faculty of Sciences, P. J. Šafárik's University, Jesenná 5, 04154 Košice, Slovak Republic

Bibliografia

• [1] M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, 1991) 42-69.
• [2] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995).
• [3] P. Mihók, G. Semaniin, Reducible properties of graphs, Discussiones Math.- Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002.
• [4] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58.
• [5] P. Mihók, On the minimal reducible bound for outerplanar and planar graphs (to appear).

Identyfikatory

DOI

10.7151/dmgt.1017