Noureddine Chikh, Miloud Mihoubi

RECITS Laboratory, Faculty of Mathematics, USTHB, Algiers, Algeria

chikh.nour@gmail.com, mmihoubi@usthb.dz

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

Keywords: threshold graphs, chromatic polynomials, generalized Bell polynomials

Mathematics Subject Classification : 05C15, 05C69, 05A18, 11B73

DOI: 10.5614/ejgta.2019.7.2.2

1. Introduction

Recall that for a given graph G = (V, E) of order n, a λ-coloring of G, λ ∈ N, is a mapping f : V → {1, 2, . . . , λ} where f(u) ̸= f(v) whenever the edge uv ∈ E. If such mapping f exists, the graph G is said to be λ-colorable, the chromatic number of G, denoted by χ (G), is the minimal value of λ for which the graph G is λ-colorable and the number of λ-colorings of G is called the chromatic polynomial P(G, λ), see [4, 8, 9]. This paper is concerned with the chromatic polynomials and the sigma polynomials of threshold graphs. These graphs was introduced by Chvatal et al. [3] and Henderson et al. [5] and have numerous applications, see for example [6]. ´ They can be constructed from an isolated vertex by repeated applications to addition a vertex to be an isolated vertex or a dominating vertex to the graph. From this definition, it follows that the complement graph G of G is also a threshold graph. The object of our investigations in this paper is, in first hand, to deduce for a given threshold graph G the chromatic polynomial P(G, λ)

Received: 6 February 2018, Revised: 5 February 2019, Accepted: 24 February 2019.

from the chromatic polynomial \(P(G,\lambda)\), and, in second hand to express the chromatic polynomials of G and \(\overline{G}\) in terms of the generalized Bell polynomials \(\mathcal{B}_{\mathbf{r},\mathbf{s}}\left(x\right)\) defined by Carlitz and studied extensively by Blasiak, Penson and Solomon, see [1, 2]. Below, we use the following notation: \((\lambda)_n = \lambda \, (\lambda-1) \cdots (\lambda-n+1)\) if \(n \geq 1\) and \((\lambda)_0 = 1\), \(G_n\) is a graph of order n and without edges with the convention \(P(G_0,\lambda)=1\).

2. Chromatic polynomials of threshold graphs

Upon using the definition of threshold graphs G and \(\overline{G}\), the following theorem gives simple expressions for their chromatic polynomials.

Theorem 2.1. Let \((G_n, n \ge 1)\) be a sequence of threshold graphs and \(G_n\) has n vertices. Then

\[P(G_n, \lambda) = \lambda (\lambda - i_{n-1}) \cdots (\lambda - i_{n-1} - \cdots - i_1),\]
\[P(\overline{G}_n, \lambda) = \lambda (\lambda - j_{n-1}) \cdots (\lambda - j_{n-1} - \cdots - j_1),\]

for some integers \(i_1, \ldots, i_{n-1}, j_1, \ldots, j_{n-1} \in \{0, 1\}\) such that \(i_k + j_k = 1, k = 1, 2, \ldots, n-1\). Furthermore, we have

\[P(G_n, \lambda) = \lambda^{r_0} (\lambda - 1)^{r_1} \cdots (\lambda - n + 1)^{r_{n-1}},\]
\[P(\overline{G}_n, \lambda) = \lambda^{s_0} (\lambda - 1)^{s_1} \cdots (\lambda - n + 1)^{s_{n-1}},\]

where

\[r_k = \sum_{l=1}^{n-1} = \delta_{(k,0)} + \delta_{(i_{n-l}+\dots+i_{n-1},k)}, \quad s_k = \sum_{l=1}^{n-1} = \delta_{(k,0)} + \delta_{(j_{n-l}+\dots+j_{n-1},k)}, \quad k = 0,\dots, n-1,\]

with \(i_0 = j_0 = 0\) and \(\delta\) is the Kronecker delta, i.e. \(\delta_{(i,j)} = 1\) if i = j and \(\delta_{(i,j)} = 0\) if \(i \neq j\).

Proof. By construction, \(G_n\) is the graph \(G_{n-1}\) plus a vertex \(x_n\) such that \(x_n\) is an isolated vertex or a dominating vertex. Similarly, by construction, \(\overline{G}_n\) is the graph \(\overline{G}_{n-1}\) plus a vertex \(x_n\) such that \(x_n\) is an isolated vertex (if it is a dominating vertex in \(G_n\)) or a dominating vertex (if it is an isolated vertex in \(G_n\)). Then, for \(n \ge 2\) we get

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

and

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

which can be written as

\[P(G_n, \lambda) = \lambda P(G_{n-1}, \lambda - i_{n-1}), n \ge 1, i_{n-1} \in \{0, 1\},\]
\(P(\overline{G}_n, \lambda) = \lambda P(\overline{G}_{n-1}, \lambda - j_{n-1}), n \ge 1, j_{n-1} = 1 - i_{n-1} \in \{0, 1\}.\)

Thus, the desired expressions follow.

Let now \(r_k\) be the order of multiplicity of a number k of the zeros of \(P\left(G_n,\lambda\right)\):

\[\{i_0, i_{n-1}, i_{n-1} + i_{n-2}, \dots, i_{n-1} + i_{n-2} + \dots i_1\}.\]

It is obvious that \(r_k = \delta_{(k,0)} + \sum_{l=1}^{n-1} \delta_{(i_{n-l}+\dots+i_{n-1},\ k)}\). Similarly we get \(s_k = \delta_{(k,0)} + \sum_{l=1}^{n-1} \delta_{(j_1+\dots+j_l,\ k)}\).

For a given threshold graph G with known chromatic polynomial \(P(G, \lambda)\), the following theorem gives the explicit expression of the chromatic polynomial \(P(\overline{G}, \lambda)\) of \(\overline{G}\).

Theorem 2.2. Let \((G_n; n \ge 1)\) be a sequence of threshold graphs and \(G_n\) has n vertices such that

\[P(G_n,\lambda) = \lambda^{r_0} (\lambda - 1)^{r_1} \cdots (\lambda - n + 1)^{r_{n-1}},\]

for some non-negative integers \(r_0, r_1, \ldots, r_{n-1}\) such that \(r_0 + r_1 + \cdots + r_{n-1} = n\). Then, the following holds

\[P\left(\overline{G}_n,\lambda\right) = \lambda\left(\lambda - r_0 + 1\right)\left(\lambda - r_0 - r_1 + 2\right)\cdots\left(\lambda - r_0 - \cdots - r_{n-2} + n - 1\right).\]

Proof. From Theorem 2.1, the chromatic polynomial \(P(G_n, \lambda)\) can be written as \(P(G_n, \lambda) = \lambda^{r_0} (\lambda - 1)^{r_1} \cdots (\lambda - n + 1)^{r_{n-1}}, \ n \geq 1\). We prove that the chromatic polynomial \(P(\overline{G}_n, \lambda)\) must be as follows

\[P\left(\overline{G}_n,\lambda\right) = \lambda \left(\lambda - r_0 + 1\right) \left(\lambda - r_0 - r_1 + 2\right) \cdots \left(\lambda - r_0 - \cdots - r_{n-2} + n - 1\right).\]

Indeed, by induction on n. The case n = 1 is obvious and assume

\[P\left(\overline{G}_n,\lambda\right) = \lambda\left(\lambda - r_0 + 1\right)\left(\lambda - r_0 - r_1 + 2\right)\cdots\left(\lambda - r_0 - \cdots - r_{n-2} + n - 1\right).\]

If \(x_{n+1}\) is an isolated vertex in \(G_{n+1}\), necessarily

\[P(G_{n+1}, \lambda) = \lambda P(G_n, \lambda)\] \[= \lambda^{r_0+1} (\lambda - 1)^{r_1} \cdots (\lambda - n + 1)^{r_{n-1}}\] \[= \lambda^{s_0} (\lambda - 1)^{s_1} \cdots (\lambda - n)^{s_n}\]

where \(s_0 = r_0 + 1\), \(s_j = r_j \ (1 \le j \le n - 1)\), \(s_n = 0\). But since \(\lambda - 1 = \lambda - s_0 - \dots - s_n + n\), we get

\[P(\overline{G}_{n+1},\lambda) = \lambda P(\overline{G}_n,\lambda-1)\] \[= \lambda (\lambda-1)(\lambda-r_0)(\lambda-r_0-r_1+1)\cdots(\lambda-r_0-\cdots-r_{n-2}+n-2)\] \[= \lambda (\lambda-s_0+1)\cdots(\lambda-s_0-\cdots-s_{n-2}+n-1)(\lambda-s_0-\cdots-s_n+n)\]

If \(x_{n+1}\) is a dominating vertex in \(G_{n+1}\), necessarily

\[P(G_{n+1}, \lambda) = \lambda P(G_n, \lambda - 1) = \lambda (\lambda - 1)^{r_0} (\lambda - 2)^{r_1} \cdots (\lambda - n)^{r_{n-1}} = \lambda^{s_0} (\lambda - 1)^{s_1} \cdots (\lambda - n)^{s_n}\]

where \(s_0 = 1\), \(s_j = r_{j-1}\) \((1 \le j \le n)\), and since \(\lambda = \lambda - s_0 + 1\) we get

\[P(\overline{G}_{n+1},\lambda) = \lambda P(\overline{G}_n,\lambda)\] \[= \lambda^2 (\lambda - r_0 + 1) (\lambda - r_0 - r_1 + 2) \cdots (\lambda - r_0 - \cdots - r_{n-2} + n - 1)\] \[= \lambda (\lambda - s_0 + 1) (\lambda - s_0 - s_1 + 2) \cdots (\lambda - s_0 - s_1 - \cdots - s_{n-1} + n)\]

So, the induction is true and produces the desired result.

Corollary 2.1. Let G be a threshold graph of n vertices. Then

\[\chi(G_n) + \chi(\overline{G}_n) = n + 1.\]

Proof. It is easy to see that

\[\chi(G_n) = 1 + \sum_{k=1}^{n-1} i_k \text{ and } \chi(\overline{G}_n) = 1 + \sum_{k=1}^{n-1} j_k,\]

which show that \(\chi(G_n) + \chi(\overline{G}_n) = 2 + \sum_{k=1}^{n-1} (i_k + j_k) = n+1\).

Corollary 2.2. Let G be a threshold graph of n vertices. Then, the sum of all zeros of the polynomial \(P(G,\lambda)\) \(P(\overline{G},\lambda)\) equals \(\frac{n(n-1)}{2}\).

Proof. Setting

\[P(G,\lambda) = \lambda^{r_0} (\lambda - 1)^{r_1} \cdots (\lambda - n + 1)^{r_{n-1}},\]
\[P(\overline{G},\lambda) = \lambda^{s_0} (\lambda - 1)^{s_1} \cdots (\lambda - n + 1)^{s_{n-1}},\]

for some non-negative integers \(r_0, r_1, \ldots, r_{n-1}\) and \(s_0, s_1, \ldots, s_{n-1}\) such that

\[r_0 + r_1 + \dots + r_{n-1} = s_0 + s_1 + \dots + s_{n-1} = n.\]

Since \(\sum_{j=0}^{n-1} jr_j\) (resp. \(\sum_{j=0}^{n-1} js_j\)) is the sum of all zeros of \(P(G, \lambda)\) (resp. \(P(\overline{G}, \lambda)\)), then, from Theorem 2.2 the sum of all zeros of the polynomial

\[P(G,\lambda) P(\overline{G},\lambda) = \lambda^{r_0+s_0} (\lambda - 1)^{r_1+s_1} \cdots (\lambda - n + 1)^{r_{n-1}+s_{n-1}}\]

is to be

\[\sum_{j=0}^{n-1} j (r_j + s_j) = \sum_{j=0}^{n-1} j r_j + 0 + (r_0 - 1) + \dots + (r_0 + \dots + r_{n-2} - (n-1))\] \[= \sum_{j=0}^{n-1} j r_j + \sum_{j=0}^{n-1} (n - 1 - j) r_j - \sum_{j=0}^{n-1} j\] \[= (n-1) \sum_{j=0}^{n-1} r_j - \frac{n(n-1)}{2}\] \[= \frac{n(n-1)}{2}.\]

3. The generalized Bell polynomials and threshold graphs

To give some connections between the chromatic polynomials and the generalized Bell polynomials (see [7]), let \(r_0, \ldots, r_{n-1}\) and \(s_0, \ldots, s_{n-1}\) be non-negative integers and set \(\mathbf{r} = (r_0, \ldots, r_{n-1})\), \(\mathbf{s} = (s_0, \ldots, s_{n-1})\). Recall that the generalized Stirling numbers of the second kind \(S_{\mathbf{r},\mathbf{s}}\) (n,k) are defined by

\[(x^{r_{n-1}}D^{s_{n-1}})\cdots(x^{r_0}D^{s_0}) = x^{d_n}\sum_{k=s_0}^{s_0+\cdots+s_{n-1}} S_{\mathbf{r},\mathbf{s}}(n,k) x^k D^k,\]

and the so-called generalized Bell polynomials \(\mathcal{B}_{\mathbf{r},\mathbf{s}}(x)\) are to be

\[(x^{r_{n-1}}D^{s_{n-1}})\cdots(x^{r_0}D^{s_0})\exp(x) = x^{d_n}\exp(x)\mathcal{B}_{\mathbf{r},\mathbf{s}}(x),\]

where

\[\mathcal{B}_{\mathbf{r},\mathbf{s}}(x) = \sum_{k=s_0}^{s_0 + \dots + s_{n-1}} S_{\mathbf{r},\mathbf{s}}(n,k) x^k \text{ and } d_n = \sum_{i=0}^{n-1} (r_i - s_i) \ge 0.\]

By choosing \(f(x) = x^{\lambda}\) in the identity

\[(x^{r_{n-1}}D^{s_{n-1}})\cdots(x^{r_0}D^{s_0}) f(x) = x^{d_n} \sum_{k=s_0}^{s_0+\cdots+s_{n-1}} S_{\mathbf{r},\mathbf{s}}(n,k) x^k D^k f(x),\]

we obtain

\[(\lambda + d_1)_{s_1} \cdots (\lambda + d_{n-1})_{s_{n-1}} = \sum_{k=s_0}^{s_0 + \dots + s_{n-1}} S_{\mathbf{r},\mathbf{s}}(n,k) (\lambda)_k,\]

where \(d_j = \sum_{i=0}^{j-1} (r_i - s_i)\), \(j \ge 1\), see a combinatorial proof in [7].

For a given sequence \((G_n, n \ge 1)\) of threshold graphs with \(G_n\) has n vertices, we prove in this section that the sequence of the sigma polynomials \((\sigma(G_n, x), n \ge 1)\) can be expressed in terms of the generalized Bell polynomials. The useful representation of the chromatic polynomial of a given graph G = (V, E) used here is

\[P(G, \lambda) = \sum_{k=\chi(G)}^{|V|} \alpha_k (G) (\lambda)_k,\]

where |V| is the number of vertices of V and \(\alpha_i(G)\) is the number of ways of partitioning V into i nonempty sets. The sigma polynomial \(\sigma(G, \lambda)\) of a graph G = (V, E) is defined by

\[\sigma(G, x) = \sum_{k=\chi(G)}^{|V|} \alpha_k(G) x^k.\]

Lemma 3.1. It holds

\[\sigma(G, x) = \exp(-x) \sum_{j>0} P(G, j) \frac{x^j}{j!}.\]

Proof. From the definition of the chromatic polynomial of G we get

\[\exp(-x) \sum_{j \ge 0} P(G, j) \frac{x^j}{j!} = \exp(-x) \sum_{j \ge 0} \left( \sum_{k=\chi(G)}^{|V|} \alpha_k (G) (j)_k \right) \frac{x^j}{j!}\] \[= \exp(-x) \sum_{k=\chi(G)}^{|V|} \alpha_k (G) x^k \sum_{j \ge k} \frac{x^{j-k}}{(j-k)!}\] \[= \sum_{k=\chi(G)}^{|V|} \alpha_k (G) x^k\] \[= \sigma(G, x).\]

The following theorem shows that some generalized Bell polynomials can be interpreted by the chromatic polynomials for the threshold graphs and gives another version of Theorem 2.2.

Theorem 3.1. It holds

\[P(G_n, \lambda) = \sum_{k=\chi(G_n)}^{n} S_{\mathbf{r},\mathbf{s}}(n, k - \chi(G_n)) (\lambda)_k,\] \[P(\overline{G}_n, \lambda) = \sum_{k=\chi(\overline{G}_n)}^{n} S_{\mathbf{r},\overline{\mathbf{s}}}(n, k - \chi(\overline{G}_n)) (\lambda)_k,\]

where

\[\mathbf{r} = (1, \dots, 1), \ \mathbf{s} = (j_0, \dots, j_{n-1}), \ \overline{\mathbf{s}} = (i_0, \dots, i_{n-1}).\]

Proof. For \(n \geq 1\) we have \(P\left(G_n, \lambda\right) = \lambda P\left(G_{n-1}, \lambda - i_{n-1}\right)\). Then, by Lemma 3.1 and the proof of Theorem 2.1 we get \(\exp\left(x\right)\sigma\left(G_n, x\right) = \sum_{k \geq 0} P(G_n, k) \frac{x^k}{k!}\).

For \(i_{n-1} = 0\) we get

\[\exp(x) \sigma(G_n, x) = \sum_{k>0} k P(G_{n-1}, k) \frac{x^k}{k!} = x \frac{d}{dx} \left( \exp(x) \sigma(G_{n-1}, x) \right),\]

and for \(i_{n-1} = 1\) we get

\[\exp(x) \, \sigma(G_n, x) = \sum_{k>0} k P(G_{n-1}, k-1) \frac{x^k}{k!} = x \exp(x) \, \sigma(G_{n-1}, x) \, .\]

Then, an equivalent expression is to be

\[\exp(x) \sigma(G_n, x) = xD^{j_{n-1}}(\exp(x) \sigma(G_{n-1}, x)), \quad j_{n-1} = 1 - i_{n-1} \in \{0, 1\}.\]

and this can be rewritten recursively as

\[\exp(x) \sigma(G_{n}, x) = xD^{j_{n-1}} (\exp(x) \sigma(G_{n-1}, x)) \vdots = (xD^{j_{n-1}}) (xD^{j_{n-2}}) \cdots (xD^{j_{1}}) (\exp(x) \sigma(G_{1}, x)) = (xD^{j_{n-1}}) (xD^{j_{n-2}}) \cdots (xD^{j_{1}}) (x \exp(x)) = (xD^{j_{n-1}}) (xD^{j_{n-2}}) \cdots (xD^{j_{0}}) \exp(x) = \exp(x) x^{d_{n}} \mathcal{B}_{\mathbf{r},\mathbf{s}}(x) = \exp(x) x^{d_{n}} \sum_{k=s_{0}}^{j_{0}+\cdots+j_{n-1}} S_{\mathbf{r},\mathbf{s}}(n,k) x^{k} = \exp(x) x^{d_{n}} \sum_{k=s_{0}}^{n-\chi(G_{n})} S_{\mathbf{r},\mathbf{s}}(n,k) x^{k}\]

where \[d_n = \sum_{k=0}^{n-1} (1 - j_k) = n - \sum_{k=1}^{n-1} j_k = n + 1 - \chi(\overline{G}_n) = \chi(G_n)\].

So we get \(\sigma\left(G_n,x\right)=\sum_{k=0}^{n-\chi(G_n)}S_{\mathbf{r},\mathbf{s}}\left(n,k\right)x^{k+\chi(G_n)}\) which gives

\[P(G_n, \lambda) = \sum_{k=0}^{n-\chi(G_n)} S_{\mathbf{r}, \mathbf{s}}(n, k) (\lambda)_{k+\chi(G_n)}.\]

The correspondent expression of \(P(\overline{G}_n, \lambda)\) can obtained by symmetry.

Acknowledgement

The authors thank the anonymous referee for his/her careful reading.

References

• [1] P. Blasiak, K.A. Penson and A.I. Solomon, The general Boson normal ordering problem. Phys. Lett. A 309 (2003), 198–205.
• [2] L. Carlitz and M.S. Klamkin, Stirling operators. Collect. Math. XXV (2) (1974), 186–211.
• [3] V. Chvátal 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.

• [4] F.M. Dong, K.M. Koh and K.L. Teo, Chromatic polynomials and chromaticity of graphs. World Scientific, British library, 2005.
• [5] 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.
• [6] N.V.R. Mahadev and U.N. Peled, Threshold graphs and related topics. Elsevier, 1995.
• [7] 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.
• [8] R.C. Read, An introduction to chromatic polynomials. J. Combin. Theory, 4 (1) (1968), 52– 71.
• [9] H.W. Zou, The chromatic uniqueness of certain complete t-partite graphs. Discrete Math. 275 (1-3) (2004), 375–383.