PDF

Discussiones Mathematicae Graph Theory  15(1) (1995)   19-31
DOI: https://doi.org/10.7151/dmgt.1003

ON CHROMATICITY OF GRAPHS

Ewa Łazuka

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

Abstract

In this paper we obtain the explicit formulas for chromatic polynomials of cacti. From the results relating to cacti we deduce the analogous formulas for the chromatic polynomials of n-gon-trees. Besides, we characterize unicyclic graphs by their chromatic polynomials. We also show that the so-called clique-forest-like graphs are chromatically equivalent.

Keywords: chromatic polynomial, chromatically equivalent graphs, chromatic characterization

1991 Mathematics Subject Classification: 05C15

References

[1]	C. Y. Chao and N. Z. Li, On trees of polygons, Archiv Math. 45 (1985) 180-185, doi: 10.1007/BF01270490.
[2]	C. Y. Chao and E. G. Whitehead Jr., On chromatic equivalence of graphs, in: Y. Alavi and D. R. Lick, ed., Theory and Applications of Graphs, Lecture Notes in Math. 642 (Springer, Berlin, 1978) 121-131.
[3]	G. L. Chia, A note on chromatic uniqueness of graphs, J. Graph Theory 10 (1986) 541-543, doi: 10.1007/BFb0070369.
[4]	B. Eisenberg, Generalized lower bounds for the chromatic polynomials, in: A. Dold and B. Eckmann, eds., Recent Trends in Graph Theory, Lecture Notes in Math. 186 (Springer, Berlin, 1971) 85-94, doi: 10.1007/BFb0059427.
[5]	F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).
[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]	R. E. Tarjan, Depth first search and linear graph algorithms, SIAM J. Comput. 1 (1972) 146-160, doi: 10.1137/0201010.
[8]	C. D. Wakelin and D. R. Woodall, Chromatic polynomials, polygon trees, and outerplanar graphs, J. Graph Theory 16 (1992) 459-466, doi: 10.1002/jgt.3190160507.
[9]	H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932) 572-579, doi: 10.1090/S0002-9904-1932-05460-X.