# On the Absolute Sum of Chromatic

Authors: Shubo Chen
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## Abstract

The absolute sum of chromatic polynomial coefficient of forest,q-tree, unicyclic graphs, and quasiwheel graphs, are determined in this paper.


---

## Body

## 1. Introduction

For a century ago, one of the most famous problems in mathematics was to prove theFour-Color Problem. During the period that the Four-Color Problem was unsolved, which spanned more than a century, many approaches were introduced with the hopes that they would lead to a solution of this famous problem. In 1913, Birkhoff [1] defined a function P(M,λ) that gives the number of proper λ-colorings of a map M for a positive integer λ. As we will see, P(M,λ) is a polynomial in λ for every map M and is called the chromatic polynomial of M. Consequently, if it could be verified that P(M,4)>0 for every map M, then this would have established the truth of the Four-Color Conjecture. In 1932, Whitney [2] expanded the study of chromatic polynomials from maps to graphs. While Whitney obtained a number of results on chromatic polynomials of graphs and others obtained results on the roots of chromatic polynomials of planar graphs, this did not contribute to a proof of the Four-Color Conjecture. Renewed interest in chromatic polynomials of graphs occurred in 1968 when Read [3] wrote a survey paper on chromatic polynomials. Let G be a graph and λ∈ℕ. A mapping f:V(G)→{1,2,…,λ} is called a λ-coloring of G if f(u)≠f(v) whenever the vertices u and v are adjacent in G. For a positive integer λ, the number of different proper λ-colorings of G is denoted by P(G,λ) and is called the chromatic polynomial of G. By convention, P(G,0)=0, and P(G,λ)≥1 if and only if G is λ-colorable. More precisely, we have (1.1)χ(G)=min⁡{λ∈N:P(G,λ)≥1}.There are many results about the coefficient of the chromatic polynomials of graphs, see related references [4–8]. In [5], the authors characterized the absolute sum of chromatic polynomial of trees, 2-trees, cycles, wheels and completed graphs, and obtained the sharp upper and lower bounds for the absolute sum of chromatic polynomial coefficients of any connected graphs. In this paper, we investigate absolute sum of chromatic polynomial coefficients of forest, q-tree, unicyclic graphs and quasiwheel graphs.


## 2. Preliminaries

LetG=(V,E) be a graph whose sets of vertices and edges are V(G) and E(G), respectively, n=|V(G)|, m=|E(G)| are the number of vertices and edges of G. E′⊆E(G), we denote by G-E′(G+E′) the subgraph of G obtained by deleting (adding) the edges of E′. W⊆V(G), G-W(G+W) denote the subgraph of G obtained by deleting (adding) the vertices of W and the edges incident with them. G·xy is the graph obtained from G by contracting x and y and removing any loop and all but one of the multiple edges, if they arise, where x,y∈V(G). Terminologies and notations not defined here can be found in [9]. The following basic results will be used and can be found in the references cited.Lemma 2.1 (see [9]).
(i) Letx and y be two nonadjacent vertices in a graph G. Then P(G,λ)=P(G+xy,λ)+P(G·xy,λ).
(ii) Lete∈E(G), then P(G,λ)=P(G-e,λ)-P(G·e,λ).
(iii) For the empty graphOn of order n, it is clear that P(On,λ)=λn. More generally, if G=⋃i=1kGi, then(2.1)P(G,λ)=∏i=1kP(Gi,λ).Lemma 2.2 (see [5]).
(i) LetG be an arbitrary graph with n vertices, then the sum of chromatic polynomial of P(G,λ)=∑i=1naiλi is
(2.2)∑i=1nai={0,m≠0,1,m=0.
(ii) LetT be an arbitrary tree with n vertices and P(T,λ)=∑i=1naiλi=λ(λ-1)n-1. Then, ∑i=1n|ai|=2n-1.
(iii) LetTn2 be an arbitrary 2-tree with n vertices and P(Tn2,λ)=∑i=1naiλi=λ(λ-1)(λ-2)n-2. Then, ∑i=1n|ai|=2·3n-2.
(iv) LetCn be an arbitrary graph with n vertices and P(Cn,λ)=∑i=1naiλi=(λ-1)n+(-1)n(λ-1). Then, ∑i=1n|ai|=2n-2.
(v) LetWn be an arbitrary graph with n vertices and P(Wn,λ)=∑i=1naiλi=λ(λ-2)n-1+(-1)n-1λ(λ-2). Then, ∑i=1n|ai|=3n-1-3.
(vi) LetKn be an arbitrary graph with n vertices and P(Kn,λ)=∑i=1naiλi=λ(λ-1)(λ-2)⋯(λ-n+1). Then, ∑i=1n|ai|=∏i=1ni.
(vii) LetG be an arbitrary connected graph with n (n>1) vertices and P(G,λ)=∑i=1naiλi, then (2.3)2n-1≤∑i=1n|ai|≤∏i=1ni.
The left equality holds if and only if G≅Tn and the right equality holds if and only if G≅Kn.
Givenq∈ℕ, the class of q-trees Tnq is defined recursively as follows: any complete graph Kq is a q-tree, and any q-tree of order n+1 is a graph obtained from a q-tree G of order n, where n≥q, by adding a new vertex and joining it to each vertex of a Kq in G. As an example, a 3-tree is depicted in Figure 1(a).The graphs 3-tree andW(8,3).
(a)
3-tree(b)
W(8,3)Lemma 2.3 (see [9]).
LetTnq is a q-tree with n vertices, then
(2.4)P(Tnq,λ)=λ(λ-1)⋯(λ-q+1).Lemma 2.4 (see [6]).
Let𝒰n(m) is a unicyclic graph order n and girth m, then
(2.5)P(Un(m),λ)=(λ-1)n+(-1)m(λ-1)n-m+1.
For1≤s≤n-2, we denote by W(n,s) the graph obtained from Wn by deleting all but s consecutive spokes. For convenience, we call W(n,s) as the quasiwheel graphs, as shown in Figure 1(b).Lemma 2.5 (see [9]).
LetW(n,s) is a quasiwheel graph with n vertices, then
(2.6)P(W(n,s),λ)=(λ-2)s-1[(λ-1)n-s+1+(-1)n-s]+(-1)n-1λ(λ-2).


## 3. Main Results

In this section, we investigate the absolute sum of chromatic polynomial coefficients of forests,q-trees, unicyclic graphs, and quasiwheel graphs.Theorem 3.1.
LetF be the forest of order n and c components and P(F,λ)=∑i=1naiλi. Then ∑i=1n|ai|=2n-c.Proof.
It is a direct result of the combination of Lemma2.1(iii) and Lemma 2.2(ii).Theorem 3.2.
LetTnq is a q-tree of order n (n≥q) and P(Tnq,λ)=∑i=1naiλi. Then ∑i=1n|ai|=q!×(q+1)n-q.Proof.
We prove the  result inductively onn.(i)
n=q. In this case Tnq≅Kq.                                        (3.1)P(Tqq,λ)=λ(λ-1)⋯(λ-q+1)=∑i=1vaiλi,
then ∑i=1v|ai|=∏i=1qi=q!.(ii)
Assume thatn=k(k≥q), let P(Tkq,λ)=∑i=1kbiλi, we have ∑i=1k|bi|=q!×(q+1)k-q.(iii)
Whenn=k+1, let P(Tk+1q,λ)=∑i=1k+1ciλi. u is a vertex with degree q, and the edges connecting u are e1, e2,…,eq, respectively. By Lemma 2.1(ii), we have
(3.2)P(Tk+1q,λ)=P(Tk+1q-e1,λ)-P(Tk+1q⋅e1,λ)=P((Tk+1q-e1)-e2,λ)-P((Tk+1q-e1)⋅e2,λ)-P(Tk+1q⋅e1,λ)=⋯=λP(Tkq,λ)-qP(Tkq,λ)=λ∑i=1kbiλi-q∑i=1kbiλi.
Then, ∑i=1k+1|ci|=∑i=1k|bi|+q∑i=1k|bi|=(q+1)×q!×(q+1)k-q=q!×(q+1)k+1-q.Combining above, the results follows.Theorem 3.3.
Let𝒰n(m) is a unicyclic graph order n and girth m and P(𝒰n(m),λ)=∑i=1naiλi. Then, ∑i=1n|ai|=2n-2n-m+1.Proof.
From Lemma2.3, we have
(3.3)P(Un(m),λ)=(λ-1)n+(-1)m(λ-1)n-m+1=∑i=0nCniλn-i(-1)i+(-1)m∑i=0n-m+1Cn-m+1iλn-m+1-i(-1)i=∑i=0m-2Cniλn-i(-1)i+∑i=m-1n[Cni(-1)i+Cn-m+1i+1-m(-1)i+1]λn-i.
Let(λ-1)n+(-1)m(λ-1)n-m+1=∑i=1naiλi, then(3.4)∑i=0n|ai|=∑i=0m-2|Cni|+∑i=m-1n|Cni-Cn-m+1i+1-m|=∑i=0m-2Cni+∑i=m-1n|Cnn-i-Cn-m+1n-i|=∑i=0m-2Cni+∑i=m-1nCnn-i-∑i=m-1nCn-m+1n-i=2n-2n-m+1.Theorem 3.4.
LetW(n,s) is a quasiwheel graph with n vertices and P(W(n,s),λ)=∑i=1naiλi. Then, ∑i=1n|ai|=3s-1(2n-s+1-1)-3.Proof.
From Lemma2.5, we have
(3.5)P(W(n,s),λ)=(λ-2)s-1[(λ-1)n-s+1+(-1)n-s]+(-1)n-1λ(λ-2)=[λs-1+⋯+Cs-11λ(-2)s-2+(-2)s-1,λn-s+1+⋯+Cn-s+12λ2(-1)n-s-1+Cn-s+11λ(-1)n-s]+(-1)n-1(λ2-2λ)=λn+⋯+[Cs-112s-2Cn-s+11(-1)n-2+Cn-s+122s-1(-1)n-2+(-1)n-1]λ2+[Cn-s+112s-1(-1)n-1+2(-1)n]λ.
Let(λ-2)s-1[(λ-1)n-s+1+(-1)n-s]=∑i=1nbiλi, then ∑i=1n|bi|=3s-1(2n-s+1-1).
Moreover,(3.6)∑i=1nbiλi=λn+⋯+[Cs-112s-2Cn-s+11(-1)n-2+Cn-s+122s-1(-1)n-2]λ2+Cn-s+112s-1(-1)n-1λ.
Thus,(3.7)∑i=1n|bi|=∑i=3n|bi|+Cs-112s-2Cn-s+11+Cn-s+122s-1+Cn-s+112s-1,∑i=1n|ai|=∑i=3n|bi|+Cs-112s-2Cn-s+11-1+Cn-s+122s-1+Cn-s+112s-1-2=3s-1(2n-s+1-1)-3.
This completes the proof.



---

*Source: 271987-2011-04-06.xml*