Note on chromatic polynomials of the threshold graphs

Noureddine Chikh, Miloud Mihoubi

Abstract


Let G be a threshold graph. In this paper, we give, in first hand, a formula relating the chromatic polynomial of Ḡ (the complement of G) to the chromatic polynomial of G. In second hand, we express the chromatic polynomials of G and Ḡ in terms of the generalized Bell polynomials.


Keywords


threshold graphs, chromatic polynomials, generalized Bell polynomials

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2019.7.2.2

References

P. Blasiak, K.A. Penson and A.I. Solomon, The general

Boson normal ordering problem. Phys. Lett. A 309 (2003), 198--205.

L. Carlitz and M.S. Klamkin, Stirling operators. Collect. Math. XXV (2) (1974), 186--211.

V. Chvatal and P.L. Hammer, Aggregation of

inequalities in integer programming in: P. L. Hammer et al. (Eds.), Studies in Integer Programming, in: Ann. Discrete Math., vol. 1. North-Holland, Amsterdam (1977), 145--162.

F.M. Dong, K.M. Koh and K.L. Teo, Chromatic

polynomials and chromaticity of graphs. World Scientific, British library,

P.B. Henderson and Y. Zalcstein, A graph-theoretic

characterization of the PV class of synchronizing primitives. SIAM

J. Comput. 6 (1) (1977), 88--108.

N.V.R. Mahadev and U.N. Peled, Threshold graphs and

related topics. Elsevier, 1995.

M.A.Mendez, P. Blasiak and K.A. Penson. Combinatorial

approach to generalized Bell and Stirling numbers and boson normal ordering problem. J. Math. Phys. 46 (8) (2005), 083511.

R.C. Read, An introduction to chromatic polynomials. J. Combin. Theory, 4 (1) (1968), 52--71.

H.W. Zou, The chromatic uniqueness of certain complete t-partite graphs. Discrete Math. 275 (1-3) (2004), 375--383.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats