����������� ������ 53 (2001), 111–116

UDK 519.175

���������� ������ ��� research paper

EXTREMAL PROPERTIES OF THE CHROMATIC POLYNOMIALS OF CONNECTED 3-CHROMATIC GRAPHS

Ioan Tomescu

Abstract. In this paper the greatest ⌈n/2⌉ values of P (G; 3) in the class of connected 3-chromatic graphs G of order n are found, where P (G; λ) denotes the chromatic polynomial of G.

1. Preliminary definitions and results

Let G be a graph of order n and let P (G; λ) be its chromatic polynomial [1]. A k-color partition of G is a partition of the vertex set V (G) into k classes where each class is an independent set of vertices. The number of k-color partitions of G and the chromatic number of G will be denoted by Col_{k}(G) and by χ(G), respectively. It is well known that P (G; λ) can be expressed in terms of the number of k-color partitions as follows

P (G; λ) = ∑_{k=1}^{n}(λ)_{k} Col_{k}(G),

where (λ)_{k} = λ(λ − 1) ⋯ (λ − k + 1).

It follows that if χ(G) = k, then Col_{k}(G) = P (G; λ)/k!. Let xy be an edge of G. By G − xy we mean the graph obtained from G by deleting edge xy. Also G/xy denotes the graph obtained from G by identifying vertices x and y, i.e., (i) by deleting both x and y and all the edges incident to them, and (ii) by introducing a new vertex z and joining z to both all the neighbors of x different from y and all the neighbors of y different from x in G.

The following lemma describes some properties of P (G; λ), which we will use later [2].

Lemma 1.1. The following properties hold:

(i) Reduction Formula. Let a and b be two adjacent vertices of G. Then P (G; λ) = P (G − ab; λ) − P (G/ab; λ).

AMS Subject Classification: 05 C 15

Keywords and phrases: Chromatic polynomial, connected 3-chromatic graph, 3-color partition, skeleton of a graph.

(ii) Let G and H be two graphs that overlap in a complete graph K_{r} on r vertices. Then the chromatic polynomial of this overlap graph is

P (G; λ)P (H; λ)/P (K_{r}; λ).

Let G be a graph and H an induced subgraph of G. The graph obtained from G by the contraction of H is the graph G_{1} derived from G by the following operations: suppress all vertices of H and the edges incident with them, and replace them with a new vertex w ∉ V (G) and edges wx such that wx ∈ E(G_{1}) if and only if there exists y ∈ V (G) such that xy ∈ E(G) and x ∈ V (G) − V (H).

The cycle with n vertices will be denoted by C_{n} and C_{n}^{1} will denote the graph consisting of C_{n} and one more vertex adjacent to only one vertex of C_{n}. The following theorem was proved in [4].

Theorem 1.2. The maximum number of 3-color partitions of a connected graph G having n vertices and chromatic number χ(G) = 3 is (2^{n−1} − 1)/3 for odd n, and (2^{n−1} − 2)/3 for even n. Moreover, if n is odd, the unique connected graph that achieves the maximum number of 3-color partitions is C_{n}, while if n is even, the unique graph is C_{n−1}^{1}.

By H(n, 2r+1) we denote the class of connected graphs G of order n containing n edges and a unique cycle C_{2r+1}, where 3 ⩽ 2r + 1 ⩽ n. It is clear that the graph deduced from G ∈ H(n, 2r + 1) by contracting C_{2r+1} is a tree on n − 2r vertices. By Rényi’s formula [3], the number of labeled graphs in H(n, 2r + 1) is equal to (n − 1)_{2r}n^{n−2r−1}/2.

Let D_{n} (n ⩾ 5) be the graph consisting of a 4-cycle in which two nonadjacent vertices are connected by a newly added path of length n−3. Note that χ(D_{n}) = 3 for even n and χ(D_{n}) = 2 for odd n. If “nonadjacent” is replaced by “adjacent”, the resulting graph is denoted by F_{n}. Hence, F_{n} consists of two cycles C_{4} and C_{n−2} having a common edge. Also, χ(F_{n}) = 3 for odd n and χ(F_{n}) = 2 for even n.

The following two properties were deduced in [5].

Lemma 1.3. For every n ⩾ 5, the following equalities hold: P (D_{n}; 3) = 2^{n} − 2^{n−2} + (−1)^{n−1}6 and P (F_{n}; 3) = 2^{n} − 2^{n−2} + (−1)^{n}6.

Theorem 1.4. (a) If G is a 2-connected graph of order n, n ⩾ 5, such that P (G; 3) is maximum in the class F_{n} \{C_{n}, K_{2,n−2}, D_{n}}, where F_{n} denotes the class of all 2-connected graphs of order n, then G ≅ F_{n} for odd n.

(b) If G is a 2-connected graph of order 6 such that P (G; 3) is maximum in the class F_{6} \ {C_{6}, K_{2,4}, F_{6}, K_{3,3} − e}, then G ≅ K_{3,3} or D_{6}.

(c) If G is a 2-connected graph of order n, n ⩾ 8, such that P (G; 3) is maximum in the class F_{n} \ {C_{n}, K_{2,n−2}, F_{n}}, then G ≅ D_{n} for even n; for n = 8 there exists another extremal graph, E_{8,3}.

Note that the graph E_{8,3}, described in [5], has χ(E_{8,3}) = 2; also χ(K_{2,n−2}) = χ(K_{3,3} − e) = χ(K_{3,3}) = 2.

Lemma 1.5. Let G be a graph of order n ⩾ 5 consisting of two cycles C_{2r+1} and C_{n−2r} having exactly one vertex in common. Then P (G; 3) < 2^{n} − 2^{n−2} − 6.

Proof. By Lemma 1.1(ii) we get

P (G; λ) = ((λ − 1)^{2r+1} − (λ − 1))((λ − 1)^{n−2r} + (−1)^{n−2r}(λ − 2))/λ

since P (C_{n}; λ) = (λ − 1)^{n} + (−1)^{n}(λ − 1). It follows that

P (G; 3) = (2^{2r+1} − 2)(2^{n−2r} + (−1)^{n−2r} + (−1)^{n−2r}2)/3
⩽ (2^{2r+1} − 2)(2^{n−2r} + 2)/3 = 2(2^{n} + 2^{2r+1} − 2^{n−2r} − 2)/3.

Since n − 2r ⩾ 3, we shall consider two subcases: Case I. 2r ⩽ n − 4, and Case II. 2r = n − 3.

Case I. If 2r ⩽ n − 4 we deduce 2(2^{n} + 2^{2r+1} − 2^{n−2r} − 2)/3 ⩽ 2(2^{n} + 2^{n−3} − 2^{4} − 2)/3 = 2^{n} − 2^{n−2} − 12 < 2^{n} − 2^{n−2} − 6.

Case II. In this case n − 2r = 3 and P (G; 3) = (2^{n−2} − 2)(2^{3} − 2)/3 < 2^{n} − 2^{n−2} − 6.

We define the skeleton S(G) of a connected graph G as follows:

(α) If G has no vertex of degree one, then S(G) = G.

(β) Otherwise, let x be a vertex of degree one of G; then G is replaced by G − x. Repeat (α).

For example, S(T) consists of a unique vertex if T is a tree, and S(G) = C_{2r+1} for any graph G ∈ H(n, 2r + 1).

Lemma 1.6. Let G be a graph of order n such that its skeleton S(G) has order r. Then P (G; λ) = P (S(G); λ)(λ − 1)^{n−r}.

Proof. One applies Lemma 1.1(ii) since P (K_{2}; λ) = λ(λ − 1).

Corollary 1.7. For every G ∈ H(n, 2r + 1), where 3 ⩽ 2r + 1 ⩽ n, we have P (G; λ) = (λ − 1)^{n} − (λ − 1)^{n−2r}.

Lemma 1.8. Let G be a connected graph of order n consisting of two vertex disjoint cycles C_{r} and C_{s}, joined by a path of length t (r + s + t = n + 1). Then

P (G; λ) = P (H; λ)(λ − 1)^{t},

where H is the graph of order r + s − 1 consisting of cycles C_{r} and C_{s} having a unique common vertex.

Proof. This equality is a consequence of Lemma 1.1(ii).

Lemma 1.9. Let G be a graph of order 2r +s+p consisting of two cycles—one cycle with s ⩾ 3 vertices and another odd cycle with 2r + 1 ⩾ 3 vertices, having in common a path of length p ⩾ 1. Then

P (G; 3) < P (H; 3) = 2^{2r+s−p} − 2^{2r+s−p−2},  (1)

where H ∈ H(2r + s − p, 3).

Proof. Suppose that the common path with p + 1 vertices of the two cycles of G has extremities a and b. It follows that 1 ⩽ p ⩽ 2r − 1 and p ⩽ s − 2. If p ⩾ 2 then vertices a and b are not adjacent and by Lemma 1.1 we deduce

P (G; λ) = P (G_{1}; λ) + P (G_{2}; λ) =

= ((λ − 1)^{s−p} + (−1)^{s−p}(λ − 1))((λ − 1)^{p} + (−1)^{p}(λ − 1))×
× ((λ − 1)^{2r−p+1} + (−1)^{2r−p+1}(λ − 1))/λ^{2}+
+ ((λ − 1)^{s−p+1} + (−1)^{s−p+1}(λ − 1))((λ − 1)^{p+1} + (−1)^{p+1}(λ − 1))×

× ((λ − 1)^{2r−p+2} + (−1)^{2r−p}(λ − 1))/(λ^{2}(λ − 1)^{2}),

where G_{1} consists of three cycles with p, s − p and 2r − p + 1 vertices having a common vertex and G_{2} of three cycles with p + 1, s − p + 1 and 2r − p + 2 vertices having a common edge. Hence (1) is equivalent to

2^{2r+s−p} > (−1)^{s}2^{2r−p+4} − 2^{s−p+3} + (−1)^{s+1}2^{p+3} + (−1)^{s−p+1}8.  (2)

For s = 3 we deduce p = 1 which contradicts our hypothesis. If s ⩾ 4 we can write 2^{2r+s−p} + (−1)^{s+1}2^{2r−p+4} ⩾ 2^{2r+s−p} − 2^{2r−p+4} = 2^{2r−p+4}(2^{s−4} − 1) ⩾ 2^{5}(2^{s−4} − 1) = 2^{s+1} − 2^{5} since p ⩽ 2r − 1. Since p ⩽ s − 2, 2^{s−p+3} + (−1)^{s}2^{p+3} ⩾ 2^{s−p+3} − 2^{p+3} = 2^{5} − 2^{s+1} for p = s − 2 and 2^{s−p+3} − 2^{p+3} ⩾ 2^{6} − 2^{s} for p ⩽ s − 3, and (2) is verified.

If p = 1 then cycles C_{s} and C_{2r+1} have an edge in common and P (G; λ) = P (C_{2r+s−1}; λ)−P (G_{3}; λ), where G_{3} consists of two cycles with s−1 and 2r vertices having a common vertex. It follows that

P (G; 3) = 2^{2r+s−1} + (−1)^{s−1}2 − (2^{s−1} + (−1)^{s−1}2)(2^{2r} + 2)/3

and (1) is equivalent to 2^{2r+s−3} > (−1)^{s}2^{2r+1} − 2^{s} + (−1)^{s−1}2. But this inequality can be deduced from (2) for p = 1 and it is also true for s = 3.

2. Main result

We shall denote by C_{n,3} the class of connected 3-chromatic graphs of order n. The following theorem is an extension of Theorem 1.2.

Theorem 2.1. Let n ⩾ 5. Then:

(a) For every r = ⌈n/2⌉ − 1, r = ⌈n/2⌉ − 2, …, 1, if G is a connected 3-chromatic graph of order n, such that P (G; 3) is maximum in the class of graphs

C_{n,3} \ ⋃_{s⩾r+1} H(n, 2s + 1),

then G ∈ H(n, 2r + 1) and P (G; 3) = 2^{n} − 2^{n−2r}.

(b) If P (G; 3) is maximum in the class of graphs

C_{n,3} \ ⋃_{s⩾1} H(n, 2s + 1),

then G ≅ F_{n} for odd n, G ≅ D_{n} for even n and in this case P (G; 3)−2^{n} −2^{n−2} −6.

Proof. (a) Let G ∈ C_{n,3}. It follows that G contains an odd cycle C_{2r+1}. If for every edge e ∈ E(G) \ E(C_{2r+1}) the graph G − e is not connected then G ∈ H(n, 2r + 1). Otherwise, by Lemma 1.1(ii) we have

P (G − e; 3) = P (G; 3) + P (G/e; 3).  (3)

But χ(G/e) = 3 since G/e contains an odd cycle even if e is a chord of C_{2r+1}. It follows that P (G/e; 3) > 0 and (3) implies that P (G − e; 3) > P (G; 3). By applying several times this operation of deleting edges not belonging to C_{2r+1} without disconnecting the resulting graph, one obtains a graph H ∈ H(n, 2r + 1) such that P (H; 3) > P (G; 3). By Corollary 1.7 if 3 ⩽ 2j + 1 < 2i + 1 ⩽ n then G_{1} ∈ H(n, 2i + 1) and G_{2} ∈ H(n, 2j + 1) imply

P (G_{1}; 3) = 2^{n} − 2^{n−2i} > 2^{n} − 2^{n−2j} = P (G_{2}; 3)

and (a) is proved for r = ⌈n/2⌉−1 (this is the property expressed by Theorem 1.2).

Let G ∈ ⋃_{s⩾2} H(n, 2s+1) and a, b be two nonadjacent vertices of G. We shall prove that if e = ab then

P (G + e; 3) < 2^{n} − 2^{n−2} = P (H; 3),  (4)

where H ∈ H(n, 3).

It is clear that the skeleton S(G + e) consists of: I. Two vertex disjoint cycles joined by a path of length t ⩾ 1; II. Two cycles having exactly one common vertex; III. Two cycles having in common a path of length p ⩾ 1. In all cases at least one cycle is odd. Suppose that |S(G + e)| = m.

Case I. In this case by Lemmas 1.6 and 1.8 one deduces

P (G + e; λ) = P (S(G + e); λ)(λ − 1)^{n−m} = P (H; λ)(λ − 1)^{n−m+t},

where H has order m − t and consists of two cycles (one is odd) having one vertex in common. By Lemma 1.5 we get

P (G + e; 3) = P (H; 3)2^{n−m+t} < (2^{m−t} − 2^{m−t−2} − 6)2^{n−m+t} < 2^{n} − 2^{n−2}.

Cases II, III. We have P (G+e; 3) < (2^{m} −2^{m−2})2^{n−m} = 2^{n} −2^{n−2} by Lemmas 1.5, 1.6 and 1.9. Let now r be such that 1 ⩽ r ⩽ ⌈n/2⌉ − 2 and G be such that P (G; 3) is maximum in the class C_{n,3}\⋃_{s⩾r+1} H(n, 2s+1). If G ∈ ⋃_{s=1}^{r} H(n, 2s+1) it follows that G ∈ H(n, 2r +1) and the property is proved. Otherwise, there exists an edge e ∈ E(G) such that G − e ∈ C_{n,3}. Since P (G; 3) is maximum in the class C_{n,3} \ ⋃_{s⩾r+1} H(n, 2s + 1), it follows that G − e ∈ ⋃_{s⩾r+1} H(n, 2s + 1), i.e., there exists a graph H in ⋃_{s⩾r+1} H(n, 2s + 1) such that G ≅ H + e. By (4) this leads to a contradiction.

(b) Let G ∈ C_{n,3}\⋃_{s⩾1} H(n, 2s+1) be such that P (g; 3) is maximum. We have seen that the greatest values of P (G; 3) in the class C_{n,3} are obtained for graphs in ⋃_{s⩾1} H(n, 2s + 1), and for graphs not belonging to this class the greatest values of P (G; 3) are obtained for graphs of the form H +e, where H ∈ ⋃_{s⩾1} H(n, 2s+1) and e ∉ E(H). It follows that G ≅ H + e, where H ∈ ⋃_{s⩾1} H(n, 2s + 1) and e ∉ E(H). Suppose that |S(H + e)| = m. As for the case (a) we may distinguish cases I–III concerning the structure of S(H + e). Using the same notation, in the case I one obtains P (H+e; 3) < (2^{m−t}−2^{m−t−2}−6)2^{n−m+t} < 2^{n}−2^{n−2}−6 since n−m+t ⩾ 1. In the case II by Lemma 1.5, P (H + e; 3) < (2^{m} − 2^{m−2} − 6)2^{n−m} ⩽ 2^{n} − 2^{n−2} − 6.

In the case III the skeleton S(H + e) is 2-connected and by Lemmas 1.3, 1.6 and Theorem 1.4 one deduces

P (H + e; 3) ⩽ (2^{m} − 2^{m−2} − 6)2^{n−m} ⩽ 2^{n} − 2^{n−2} − 6

and equality holds if and only if m = n and G ≅ F_{n} for odd n and G ≅ D_{n} for even n.

Note that Col_{3}(F_{n}) for odd n, resp. Col_{3}(D_{n}) for even n is equal to Col_{3}(H) − 1 = 2^{n−3} − 1 for any H ∈ H(n, 3).

REFERENCES

[1] G.D. Birkhoff, A determinantal formula for the number of ways of coloring a map, Ann. Math. (2) 14 (1912), 42–46.

[2] R.C. Read, An introduction to chromatic polynomials, J. Combinatorial Theory 4 (1968), 52–71.

[3] A. Rényi, On connected graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl 4 (1959), 385–388.

[4] I. Tomescu, Le nombre maximal de 3-coloration d’un graphe connexe, Discrete Math. 1 (1972), 351–356.

[5] I. Tomescu, Maximum chromatic polynomial of 3-chromatic blocks, Discrete Math. 172 (1997), 131–139.

(received 25.01.2001)

University of Bucharest, Faculty of Mathematics, Str. Academiei 14, 70109 Bucuresti, Romania E-mail: ioan@math.math.unibuc.ro