On chromaticity of graphs
Ewa Łazuka
Discussiones Mathematicae Graph Theory, Tome 15 (1995), p. 19-31 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1995-01-01
EUDML-ID : urn:eudml:doc:270453 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1003,
     author = {Ewa \L azuka},
     title = {On chromaticity of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {15},
     year = {1995},
     pages = {19-31},
     zbl = {0832.05041},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1003}
}

Ewa Łazuka. On chromaticity of graphs. Discussiones Mathematicae Graph Theory, Tome 15 (1995) pp. 19-31. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1003/

[000] [1] C. Y. Chao and N. Z. Li, On trees of polygons, Archiv Math. 45 (1985) 180-185, doi: 10.1007/BF01270490. | Zbl 0575.05027

[001] [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.

[002] [3] G. L. Chia, A note on chromatic uniqueness of graphs, J. Graph Theory 10 (1986) 541-543, doi: 10.1007/BFb0070369. | Zbl 0616.05035

[003] [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.

[004] [5] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).

[005] [6] R. C. Read, An introduction to chromatic polynomials, J. Combin. Theory. 4 (1968) 52-71, doi: 10.1016/S0021-9800(68)80087-0. | Zbl 0173.26203

[006] [7] R. E. Tarjan, Depth first search and linear graph algorithms, SIAM J. Comput. 1 (1972) 146-160, doi: 10.1137/0201010. | Zbl 0251.05107

[007] [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. | Zbl 0778.05074

[008] [9] H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932) 572-579, doi: 10.1090/S0002-9904-1932-05460-X. | Zbl 0005.14602