Download PDF - On chromaticity of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On chromaticity of graphs

Authors 1

Affiliations

  1. Department of Applied Mathematics, Technical University of Lublin

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

ENG
chromatic polynomial, chromatically equivalent graphs, chromatic characterization

Bibliography

  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.
Discussiones Mathematicae Graph Theory
1995/15/1
Export to PBN, Opens in new tab
Pages:
19-31
Main language of publication
English
Received
1994-02-17
Accepted
1994-07-09
Published
1995
Exact and natural sciences