DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 20(2) (2000) 293-301
DOI: 10.7151/dmgt.1128

CHROMATIC POLYNOMIALS OF HYPERGRAPHS

Mieczysław Borowiecki

Institute of Mathematics, Technical University of Zielona Góra
Podgórna 50, 65-246 Zielona Góra, Poland
e-mail: m.borowiecki@im.uz.zgora.pl

Ewa Łazuka

Department of Applied Mathematics, Technical University of Lublin
Bernardyńska 13, 20-950 Lublin, Poland

e-mail: elazuka@antenor.pol.lublin.pl

Abstract

In this paper we present some hypergraphs which are chromatically characterized by their chromatic polynomials. It occurs that these hypergraphs are chromatically unique. Moreover we give some equalities for the chromatic polynomials of hypergraphs generalizing known results for graphs and hypergraphs of Read and Dohmen.

Keywords: chromatic polynomial, chromatically unique hypergraphs, chromatic characterization.

2000 Mathematics Subject Classification: 05C15.

References

[1] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973).
[2] C.Y. Chao and E.G. Whitehead Jr., On chromatic equivalence of graphs, in: Y. Alavi and D.R. Lick, eds., Theory and Applications of Graphs, Lecture Notes in Math. 642 (Springer, Berlin, 1978) 121-131, doi: 10.1007/BFb0070369.
[3] K. Dohmen, Chromatische Polynome von Graphen und Hypergraphen, Dissertation (Düsseldorf, 1993).
[4] T. Helgason, Aspects of the theory of hypermatroids, in: C. Berge and D. Ray-Chaudhuri, eds., Hypergraph Seminar, Ohio State University 1972, Lecture Notes in Mathematics 411 (Springer-Verlag, 1974) 191-213.
[5] R.P. Jones, Some results of chromatic hypergraph theory proved by ``reduction to graphs", Colloque CNRS. Problémes Combinatoires et Théorie des Graphes 260 (1976) 249-250.
[6] R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968) 52-71, doi: 10.1016/S0021-9800(68)80087-0.
[7] I. Tomescu, Chromatic coefficients of linear uniform hypergraphs, J. Combin. Theory (B) 260 (1998) 229-235, doi: 10.1006/jctb.1997.1811.

Received 18 October 2000