Building Fences Around the Chromatic Coefficients Debra Mullins Strickland DEPARTMENT OF MATHEMATICS THE UNIVERSITY OF OKLAHOMA NORMAN, OK 73019-0315 E-mail: dmstric@ibm.net Received October 18, 1995; revised May 19, 1997 Abstract: Associated to each graph G is its chromatic polynomial f (G, t) and we associate to f (G, t) the sequence α(G) of the norms of its coefficients. A stringent partial ordering is established for such sequences. The main result is that for any graph G with q edges we have α(Rq ) ≤ α(G) ≤ α(Sq ), where Rq and Sq are specified graphs with q edges. This translates into a clearer view of allowable values and patterns in the c 1997 John Wiley & Sons, Inc. J Graph Theory 26: 123–128, 1997 chromatic coefficients. Keywords: chromatic polynomials, partially ordered sets 1. INTRODUCTION The chromatic polynomial f (G, t) of a graph G counts the number of proper t-colorings of G. Let G have p points, q edges, and k components. It is well known (see [1] and [2]) that: f (G, t) is a monic polynomial of degree p, the coefficient of tp−1 is −q, the coefficients alternate in sign, and ti has nonzero coefficient if and only if k ≤ i ≤ p. If f (G, t) = a0 tp − a1 tp−1 + · · · + (−1)p−k ap−k tk then we define the chromatic sequence of G to be α(G) = (a0 , a1 , . . . , am ), where m = p − k. Here a0 = 1 and a1 = q unless q = 0, when α(G) = (1). By design, graphs with different numbers of points can have the same chromatic sequence. In particular, if H = G ∪ K1 , then f (H, t) = tf (G, t) and thus α(H) = α(G); that is, isolated points have no impact on the chromatic sequence. Figure 1 illustrates the chromatic sequences up to q = 6. After some initial set-up with sequence operations and partial orderings, we will first compare α(H) with α(G) when H ⊂ G. Then, among all graphs with q edges we will identify graphs Rq c 1997 John Wiley & Sons, Inc. CCC 0364-9024/97/030123-06 124 JOURNAL OF GRAPH THEORY FIGURE 1. Chromatic sequences for small q . (containing many cycles) and Sq (containing no cycles) whose chromatic coefficients form bounds for the chromatic coefficients of any graph G with q edges. By means of the particular partial ordering employed, we will gain some understanding of the manner in which the coefficients for G can deviate from the coefficients for Rq and Sq . FENCES AROUND CHROMATIC COEFFICIENTS 125 We write E(G) for the edge-set of G and G/x for the result of contracting edge x in G. 2. SEQUENCE OPERATIONS Let P be the collection of all nonempty finite sequences of positive integers. If A = (a0 , a1 , . . . , am ) ∈ P, we write l(A) = m and adopt the convention that ai = 0 if i > l(A). If A and B = (b0 , b1 , . . . , bn ) ∈ P and d ∈ N, we define A + B = (a0 + b0 , a1 + b1 , . . . , at + bt ) where t = max(m, n), A +→ B = (a0 , a1 + b0 , . . . , at + bt−1 ) where t = max(m, n + 1), and dA = (da0 , da1 , . . . , dam ). / P. Although We also adopt the convention that A + 0B = A +→ 0B = A even though 0B ∈ +→ is not associative, one may readily check that (A +→ B) +→ (C +→ D) = A +→ [(B + C) +→ D]. (1) We may compare sequences A and B in P and write A ≤ B if: (τ1 ) (τ2 ) (τ3 ) a0 = b0 , ai ≤ bi for all i, and whenever aj = bj with 1 ≤ j ≤ l(B) then ai = bi for 1 ≤ i ≤ j. Note that A ≤ B necessitates l(A) ≤ l(B). We write A < B to indicate A ≤ B and A = / B; we write A B to indicate A < B with ai < bi for 1 ≤ i ≤ l(B). It is straightforward to check that ≤, <, and are transitive. Caution is required when combining the sequence operations with the orderings. For example, (A ≤ B and C ≤ D) does not imply (A +→ C ≤ B +→ D) as can be seen with A = (1, 2), B = (1, 2, 1), and C = D = (1, 2, 3). Then A +→ C = (1, 3, 2, 3) and B +→ D = (1, 3, 3, 3), two sequences which cannot be compared using ≤. However, we have the following results. Proposition 2.1. Let A, B, C ∈ P and d, e ∈ N ∪ {0}. (a) (b) (c) (d) (e) If A ≤ C and B < C then A +→ B < C +→ C. If B ≤ C and l(A) ≤ l(C) + 1 then A +→ B ≤ A +→ C. If A ≤ B then A +→ dA ≤ B +→ dB. If A ≤ B and A ≤ C then A + A ≤ B + C. If d ≤ e then A +→ dA ≤ A +→ eA. Proof. It is easy to see that τ1 and τ2 are satisfied in each case. We will show that τ3 is satisfied in case (b), since it is the least obvious. Assume B ≤ C and l(A) ≤ l(C) + 1. If aj + bj−1 = aj + cj−1 for some j satisfying 1 ≤ j ≤ l(A +→ C) then bj−1 = cj−1 , and since l(A +→ C) = max{l(A), l(C) + 1} = l(C) + 1 we have j − 1 ≤ l(C). Now B ≤ C implies b0 = c0 and bi = ci for 1 ≤ i ≤ j − 1 and we conclude that ai + bi−1 = ai + ci−1 for 1 ≤ i ≤ j. The verifications of τ3 for cases (a), (c), (d) and (e) are similar, and case (a) also requires the / C +→ C. observation that A +→ B = 126 JOURNAL OF GRAPH THEORY 3. THE CHROMATIC SEQUENCE OF A SUBGRAPH Theorem 12.32 in [1], reformulated, gives f (G, t) = f (G − x, t) − f (G/x, t) for each edge x of G. Because these polynomials have coefficients which alternate in sign, and since f (G/x, t) has degree one less than f (G, t), we have α(G) = α(G − x) +→ α(G/x). This is called the reduction formula because both G − x and G/x have fewer edges than G. Lemma 3.1. If H ⊂ G then α(H) α(G) unless E(H) = E(G) when α(H) = α(G). Proof. If E(H) = E(G) then H and G differ only in their isolated points. Now assume that E(G) \ E(H) = {x1 , . . . , xn } where n ≥ 1. Then G/x1 has the same number of components as G and one less point, and so l(α(G/x1 )) = l(α(G)) − 1. The reduction formula says α(G) = α(G − x1 ) +→ α(G/x1 ) and we immediately conclude that α(G − x1 ) α(G). With n applications of this procedure we arrive at α(H) · · · α(G − x1 ) α(G). By the technique of the proof we know the following: if H ⊂ G with α(H) = (1, h1 , . . . , hk ) and α(G) = (1, g1 , . . . , gm ), and |E(G) \ E(H)| = n, then hi ≤ gi − n for 1 ≤ i ≤ k. A related observation which we will use later is that when gm = 1 every edge of G is a bridge, for if x is any edge of G we will have l(α(G − x)) < l(α(G)) and thus G − x has more components than G. 4. THE UPPER BOUND FOR CHROMATIC SEQUENCES For q ≥ 0 we could choose Sq to be any acyclic graph with q edges; for the sake of being specifific, we choose Sq to be the star. If x ∈ E(Sq ) then the reduction formula gives α(Sq ) = α(Sq − x) +→ α(Sq /x) = α(Sq−1 ) +→ α(Sq−1 ). If m < n we have Sm ⊂ Sn , and Lemma 3.1 implies α(Sm ) α(Sn ). Theorem 4.1. If |E(G)| = q then α(G) ≤ α(Sq ). Equality occurs if and only if G has no cycles. Proof. From Theorem 12.35 in [1] we have: A graph G with p points is a tree if and only if f (G, t) = t(t − 1)p−1 . In particular, f (Sq , t) = t(t − 1)q . If α(G) = α(Sq ) then α(G) has terminal value 1, implying that every edge of G is a bridge and thus G has no cycles. If G has no cycles, we apply Theorem 12.35 to the k components of G and since the chromatic polynomial is multiplicative over components, we have f (G, t) = tk (t − 1)q yielding α(G) = α(Sq ). What remains is to show that if G has q edges and at least one cycle then α(G) < α(Sq ). This is vacuously true for q = 0, 1, 2. Assume q ≥ 3. Let C be a cycle in G and let x ∈ E(C). Since |E(G − x)| = q − 1 and |E(G/x)| = q 0 for some q 0 ≤ q − 1 we may assume by induction that α(G − x) ≤ α(Sq−1 ) and α(G/x) ≤ α(Sq0 ). If G/x has a cycle then, again by induction, α(G/x) < α(Sq0 ) ≤ α(Sq−1 ). If not, then C must be a triangle, and so q 0 ≤ q − 2 giving α(G/x) = α(Sq0 ) ≤ α(Sq−2 ) < α(Sq−1 ). Either way, α(G/x) < α(Sq−1 ), and the reduction formula and Proposition 2.1(a) give α(G) = α(G − x) +→ α(G/x) < α(Sq−1 ) +→ α(Sq−1 ) = α(Sq ). This result would allow us to say, for example, that A = (1, 6, 15, 18, 14, 6) is not the chromatic sequence for any graph. If A were the chromatic sequence for some graph G, then G would FENCES AROUND CHROMATIC COEFFICIENTS 127 necessarily have 6 edges and by Theorem 4.1 we would have α(G) ≤ α(S6 ) = (1, 6, 15, 20, 15, 6, 1). Since A does not compare properly with α(S6 ) we know that no such graph exists. 5. THE LOWER BOUND FOR CHROMATIC SEQUENCES Having shown that graphs with no cycles produce upper bounds for the chromatic sequences, it is natural to expect that graphs with many cycles produce lower bounds. It is straightforward to see that for the complete graphs we have f (K1 , t) = t and f (Kp , t) = t(t − 1) · · · (t − p + 1) = (t − p + 1)f (Kp−1 , t) if p ≥ 2; that is α(K1 ) = (1) and α(Kp ) = α(Kp−1 ) +→ (p − 1)α(Kp−1 ) if p ≥ 2. For a fixed q we let π(q) = max{i|(2i ) ≤ q} so that q = (m 2 ) + r with m = π(q) and 0 ≤ r ≤ m − 1, and define Rq to be the unique connected graph with q edges satisfying Km ⊆ Rq ⊂ Km+1 . Then f (Rq , t) = f (Km , t) if r = 0, and f (Rq , t) = (t − r)f (Km , t) if r > 0, yielding α(Rq ) = α(Km ) +→ rα(Km ). If j < k we have Rj ⊂ Rk and conclude from Lemma 3.1 that α(Rj ) α(Rk ). Proposition 5.1. If q ≥ 1 and 0 ≤ d ≤ π(q) − 1 then α(Rq ) ≤ α(Rq−d ) +→ dα(Rq−d ). Proof. We have q = (m 2 ) + r where m = π(q) and 0 ≤ r ≤ m − 1. If d ≤ r then ) + r − d where 0 ≤ r − d ≤ m − 1. Thus, writing A = α(Km ) and using (1) and q − d = (m 2 Propositions 2.1(b) and (e), α(Rq−d ) +→ dα(Rq−d ) = [A +→ (r − d)A] +→ d[A +→ (r − d)A] = A +→ [rA +→ d(r − d)A] ≥ A +→ rA = α(Rq ). m−1 Thus we may suppose that d > r. Then q − d = (m 2 ) + r − d = ( 2 ) + δ where 0 ≤ δ = m − 1 + r − d ≤ m − 2. Note that if z = d − r > 0 then dδ = d(m − 1 + r − d) = (r + z)(m − 1 − z) = r(m − 1) + z(m − 1 − r − z) ≥ r(m − 1) (2) since r + z = d ≤ m − 1. Writing A = α(Km ) and B = α(Km−1 ), and using (1), and Proposition 2.1(b) and (e) we have α(Rq ) = A +→ rA = [B +→ (m − 1)B] +→ r[B +→ (m − 1)B] = B +→ [(m − 1 + r)B +→ r(m − 1)B] and α(Rq−d ) +→ dα(Rq−d ) = [B +→ δB] +→ d[B +→ δB] = B +→ [(δ + d)B +→ dδB] ≥ α(Rq ) since δ + d = m − 1 + r and dδ ≥ r(m − 1) by (2). Proposition 5.1 fails if d ≥ π(q). Consider q = 5 (so π(q) = 3) and d = 3. Then α(R5 ) = (1, 5, 8, 4) ≤ / (1, 5, 7, 3) = (1, 2, 1) +→ 3(1, 2, 1) = α(R2 ) +→ 3α(R2 ). 128 JOURNAL OF GRAPH THEORY Before moving on to the main theorem, we observe that if G has q ≥ 1 edges then there must be a point in G with degree d satisfying 0 < d ≤ π(q) − 1. This follows from noting that G has at least as many nonisolated points as Rq , so the average degree (see Theorem 2.1 in [1]) among G’s nonisolated points cannot exceed the average degree in Rq , and the average degree in Rq is strictly less than π(q). Theorem 5.2. If |E(G)| = q then α(Rq ) ≤ α(G). Proof. By induction on q. If q = 0 we have α(Rq ) = (1) = α(G). Now assume that q ≥ 1 and write q = (m 2 ) + r where m = π(q) and 0 ≤ r ≤ m − 1. There is a point w in G with degree d satisfying 0 < d ≤ m − 1. Let L = G − w and let x1 , . . . , xd be the edges incident with w. Repeated application of the reduction formula and (1) yields α(G) = α(G−{x1 , . . . , xd })+→ Pd (α(G/x1 ) + i=2 α((G − {x1 , . . . , xi−1 })/xi )). Note that α(L) = α(G − {x1 , . . . , xd }) and L is a subgraph of all the contraction graphs in the summation so by Lemma 3.1 and Proposition Pd 2.1(d) we have dα(L) ≤ (α(G/x1 ) + i=2 α((G − {x1 , . . . , xi−1 })/xi )). Now by 2.1(b) we have α(G) ≥ α(L) +→ dα(L). Since |E(L)| = q − d ≤ q − 1 we may assume, by induction, that α(Rq−d ) ≤ α(L) and thus Propositions 5.1 and 2.1(c) yield α(Rq ) ≤ α(Rq−d ) +→ dα(Rq−d ) ≤ α(L) +→ dα(L) ≤ α(G). 6. SUMMARY Theorems 4.1 and 5.2 combine to produce the main result: if G is a graph with q edges then α(Rq ) ≤ α(G) ≤ α(Sq ). Continuing our prior discussion we may conclude, for example, that if G is a graph with 6 edges then (1, 6, 11, 6) ≤ α(G) ≤ (1, 6, 15, 20, 15, 6, 1). Since the chromatic sequences for the Rq and Sq graphs are particularly easy to calculate, this provides us with a rapid means for dispensing with many polynomials which might otherwise appear to be potentially chromatic. These results will appear in the author’s dissertation. Many helpful comments and interesting observations were provided by the referees. In particular it was suggested that these results might carry over to matroids, with proofs made possible using the broken circuit complex. References [1] F. Harary, Graph Theory, Addison-Wesley, Reading, MA (1969). [2] H. Whitney, The coloring of graphs, Ann. Math. (2) 33 (1932), 688–718.

1/--страниц