Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties

• Autorzy: Ewa Drgas-Burchardt
• Języki publikacji: EN

Abstrakty

EN

An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let $L^a$ denote a class of all such properties. In the paper, we consider H-reducible over $L^a$ properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.

Słowa kluczowe

EN

hereditary graph property; lattice of additive hereditary graph properties; minimal forbidden graph family; join in the lattice; reducibility

Kategorie tematyczne

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

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2009
• Tom: 29
• Numer: 2
• Strony: 263-274

Daty

wydano

2009

otrzymano

2007-12-21

poprawiono

2008-09-26

zaakceptowano

2008-12-01

Twórcy

autor

Ewa Drgas-Burchardt

• Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland

Bibliografia

• [1] A.J. Berger, Minimal forbidden subgraphs of reducible graph properties, Discuss. Math. Graph Theory 21 (2001) 111-117, doi: 10.7151/dmgt.1136.
• [2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1981).
• [3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishawa International Publication, Gulbarga, 1991) 41-68.
• [4] M. Borowiecki, I. Broere, M. Frick, P.Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
• [5] E.J. Cockayne, Colour classes for r-graphs, Canad. Math. Bull. 15 (1972) 349-354, doi: 10.4153/CMB-1972-063-2.
• [6] E. Drgas-Burchardt, On uniqueness of a general factorization of graph properties, submitted.
• [7] E. Drgas-Burchardt, A note on joins of additive hereditary graph properties, Discuss. Math. Graph Theory 26 (2006) 413-418, doi: 10.7151/dmgt.1333.
• [8] M. Frick, A survey of (m,k)-colorings, in: J. Gimbel et al. (Eds), Quo Vadis Graph Theory? A source book for challenges and directions, Annals Discrete Math. 55 (North-Holland, Amsterdam, 1993) 45-57, doi: 10.1016/S0167-5060(08)70374-1.
• [9] D.L. Greenwell, R.L. Hemminger and J. Klerlein, Forbidden subgraphs, in: Proceedings of the 4th S-E Conf. Combinatorics, Graph Theory and Computing (Utilitas Math., Winnipeg, Man., 1973) 389-394.
• [10] G. Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. 2 (1952) 326-336, doi: 10.1112/plms/s3-2.1.326.
• [11] J. Jakubik, On the Lattice of Additive Hereditary Properties of Finite Graphs, Discuss. Math. General Algebra and Applications 22 (2002) 73-86.
• [12] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q.
• [13] N. Robertson and P.D. Seymour, Graph minors - a survey, in: Surveys in Combinatorics 1985 (Glasgow, 1985), London Math. Soc. Lecture Note Ser. 103 (Cambridge University Press., Cambridge 1985), 153-171.

Identyfikatory

DOI

10.7151/dmgt.1446