Maximal hypergraphs with respect to the bounded cost hereditary property

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

Abstrakty

EN

The hereditary property of hypergraphs generated by the cost colouring notion is considered in the paper. First, we characterize all maximal graphs with respect to this property. Second, we give the generating function for the sequence describing the number of such graphs with the numbered order. Finally, we construct a maximal hypergraph for each admissible number of vertices showing some density property. All results can be applied to the problem of information storage.

Słowa kluczowe

EN

cost colouring; hereditary property; maximal hypergraphs

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C65: Hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2005
• Tom: 25
• Numer: 1-2
• Strony: 67-77

Daty

wydano

2005

otrzymano

2003-10-30

poprawiono

2004-12-09

Twórcy

autor

Ewa Drgas-Burchardt

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

autor

Anna Fiedorowicz

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

Bibliografia

• [1] C. Berge, Hypergraphs (North-Holland, Amsterdam, 1989).
• [2] E. Kubicka and A.J. Schwenk, An introduction to chromatic sums, in: Proceedings of the Seventeenth, Annual ACM Computer Sciences Conference (ACM Press) (1989) 39-45.
• [3] J. Mitchem and P. Morriss, On the cost chromatic number of graphs, Discrete Math. 171 (1997) 201-211, doi: 10.1016/S0012-365X(96)00005-2.
• [4] J. Riordan, An Introduction to Combinatorial Analysis (New York, 1958).

Identyfikatory

DOI

10.7151/dmgt.1261