close

Вход

Забыли?

вход по аккаунту

?

327

код для вставкиСкачать
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.
Документ
Категория
Без категории
Просмотров
2
Размер файла
122 Кб
Теги
327
1/--страниц
Пожаловаться на содержимое документа