Line Graphs and their Chromatic Polynomials

Line Graphs and their Chromatic Polynomials

Annals of Discrete Mathematics 13 (1982) 15-22 0 North-Holland Publishing Company LINE GRAPHS AND THEIR CHROMATIC POLYNOMIALS RUTH A. BAR1 George Was...

315KB Sizes 0 Downloads 38 Views

Annals of Discrete Mathematics 13 (1982) 15-22 0 North-Holland Publishing Company

LINE GRAPHS AND THEIR CHROMATIC POLYNOMIALS RUTH A. BAR1 George Washington University Washington, D.C.20052 U.S.A. Let G be a connected (p,q)-graph with q > 0 , and let Denote the chromatic L(G) be the line graph of G polynomial of G by P(G,X), and the line chromial of G, that is, the chromatic polynomial of L(G), by PL(G;A). Since L(G) has relatively many lines, it is most convenient to compute the line chromial of G in factorial form. A useful method for computing PL(G,A) in this form is to multiply the partition matrix of the lines of G by the adjacency vector of L(G) By this method, certain relations are derived between the points and lines of G and the coefficients of PL(G,A). An appendix gives the coefficient vectors for the factorial forms of P(G,A) and PL(G,X) for all connected (p,q)-graphs with p S 5 and O < q s 8 .

.

.

1.

Introduction The definitions and notation in this paper are based on C21. In addition, we will need the following definitions. Let G be a (p,q)-graph whose lines have been labelled with integers 1,2,...,q, The and let L(G) , the line graph of G , be a (pL,qL)-graph. adjacency v e c t o h of L(G) is the column vector lT , with entries AL = Ca12,a13,...,a l q ~ a 2 3 ~ a 2 4 ~ . . . ~ a 2 q ~ .q-lrq ..~a a for all pairs i, j such that i j s q , where a = 1 if ij ij lines i and j are adjacent, and aij is 0 otherwise. If n is a partition of the lines of G into k parts, 1 s k 5 q , the paktitio n v e c t o k of n is the vector P = Cp12,p131.. Iplqr~231p24r.. I j s q , where pij = 1 PZq' * * * lPq-lrqI , with entries pij for all i if lines i and j are in the same cell of n , and pij = 0 if i and j are in distinct cells of n A A - c o e o k i n g of L(G) is a function from the set of lines of G into the set I A = {lI2,...,A1 , wbse elements,are called c o e o k d . A A-coloring is p k o p e h if no two

.

.

15

.

R.A. Ban

16

a d j a c e n t l i n e s a r e a s s i g n e d t h e same c o l o r .

Associated with each

X-coloring of L ( G ) , t h e r e i s a p a r t i t i o n o f t h e l i n e s o f G i n t o c o l o r classes. A c o t o h ceabd i s a s e t o f i n d e p e n d e n t l i n e s o f G o r a matching. A c o t o h p a h t i t i o n of L(G) is a p a r t i t i o n of t h e l i n e s of G i n t o c o l o r c l a s s e s . I f a c o l o r p a r t i t i o n TI h a s k c o l o r classes, t h e number o f p r o p e r X-colorings a s s o c i a t e d w i t h

,

is = X(X-1) (A-2) (A-k+l) Thus, i f P L ( G , X ) denotes the Line chhomiaL 0 6 G , i . e . t h e c h r o m a t i c polynomial o f L ( G ) , t h e s e t o f a l l c o l o r p a r t i t i o n s of t h e l i n e s of G l e a d s t o t h e f a c t o r i a l form

.

...

of

PL(G,X) PL(G,A)

TI

P

= boX(q)

+

+

blX(q-l)

b2X(q-2)

+...+

bq-lX

bi i s t h e number o f p a r t i t i o n s o f t h e l i n e s o f G i n t o q - i c o l o r classes. The S t i h L i n g numbehd 0 6 t h e d i h d t kind, d e n o t e d s ( n , r ) , a r e d e f i n e d

where

.

f

= X ( X - 1 ) . ..(X-n+l) = s ( n , r ) Xr I t follows by t h e r e l a t i o n r= n from t h i s d e f i n i t i o n t h a t s ( n , n ) = 1, s ( n , n - l ? = - ( 2 ) , ‘ n-1 s ( n , l ) = (-1) (n-1) I , and s ( n , O ) = 0 The qxq S t i h t i n g mathiX 0 6 t h e d i h b t kind i s t h e m a t r i x Sl,q whose e n t r i e s a r e S t i r l i n g

.

numbers o f t h e f i r s t k i n d , where

Let

PL(G,X)

=

q-1 C

i=o

biX(q-i)

=

q-1 C

i=O

be t h e l i n e c h r o m i a l - o f

cihq-i

G

i n f a c t o r i a l and s t a n d a r d forms r e s p e c t i v e l y , and l e t

...,

and C = Cco,cl, c 1 be t h e i r r e s p e c t i v e q- 1 Then it i s c l e a r t h a t B.S1 = C *q Counting t h e c o l o r p a r t i t i o n s o f L ( G )

B = Cbo,bl,...,bq-ll

coefficient vectors. 2.

.

.

The f o l l o w i n g approach t o c o u n t i n g c o l o r p a r t i t i o n s i s a m o d i f i c a t i o n o f t h e method i n t r o d u c e d by O’Connor C31 Theorem 1. L e t n be an a r b i t r a r y p a r t i t i o n o f t h e l i n e s of G into k parts. L e t P be t h e p a r t i t i o n v e c t o r o f n , and l e t AL

.

.

be t h e a d j a c e n c y v e c t o r o f L ( G ) Then n i s a c o l o r p a r t i t i o n o f L ( G ) i f and o n l y i f t h e s c a l a r p r o d u c t P.% = 0 Proof. Suppose ’ n i s a c o l o r p a r t i t i o n o f L ( G ) Then i f l i n e s i and j a r e i n t h e same c e l l o f n , t h e y a r e i n d e p e n d e n t , so pij = 1 implies a = 0 , and a = 1 implies p = 0 for a l l

.

ij

ij

i j

.

Line graphs and their chromatic polynomials

.

17

.

p a i r s i , j of l i n e s of G Thus P.% = 0 C o n v e r s e l y , i f ‘TI i s n o t a c o l o r p a r t i t i o n of L ( G ) , t h e n some c e l l of T c o n t a i n s a n a d j a c e n t p a i r of l i n e s , i and j Thus p i j = 1 and a = 1 ,

.

.

ij

p i j a i j = 1 , and P.AL # 0 0 Suppose t h a t AL h a s e x a c t l y r 0 - e n t r i e s . Then G h a s r p a i r s o f non-adjacent l i n e s , o r 2 - l i n e matchings. L e t M = {ml~m2,...,m,~ b e t h e s e t o f 2 - l i n e matchings o f G . Then e v e r y matching of G i s e i t h e r a s i n g l e l i n e o r a u n i o n of 2 - l i n e

so

matchings. A partition

‘TI i s an M - p a h t i t i o n o f t h e l i n e s of G i f e a c h c e l l of n c o n t a i n s e i t h e r a s i n g l e l i n e o r a u n i o n of 2 - l i n e matchings of G The p a h t i t i o n m a t h i x PM of L ( G ) i s t h e m a t r i x whose rows a r e t h e p a r t i t i o n v e c t o r s o f t h o s e M - p a r t i t i o n s o f L ( G ) which have a t l e a s t A p a r t s . I n PM , a p a r t i t i o n v e c t o r i s s a i d t o b e The a t Levee k i f i t r e p r e s e n t s a k - p a r t M - p a r t i t i o n o f L ( G ) vectors a t l e v e l q , q - l , A a p p e a r i n t h a t o r d e r i n PM , b u t t h e o r d e r o f t h e v e c t o r s w i t h i n t h e same l e v e l i s a r b i t r a r y . D i f f e r e n t l e v e l s a r e s e p a r a t e d by dashed l i n e s . Example 1

.

.

...,

G =

3Q5

A = 3

1 2 1 3 1 4 15 23 2 4 25 34 35 45 AL = C 1 ,

1, 0, 0, 1, 1, 1, 1, 0, 1 1

M = [{l,4l,~l,5lI~3,5l) M-parti t i o n s 5 parts: 1;2;3;4;5 4 parts: 1,4;2;3;5 1,5;2;3;4 3 parts: 1,4,5;2;3 1,4;3,5;2 P a r t i t i o n matrix PM(G)

3,5;1;2;4 1,3,5;2;4

R.A. Ban

18

Theorem 2 .

The number o f z e r o s i n t h e v e c t o r

number o f c o l o r p a r t i t i o n s of

.

L(G)

Pw.k = D

is t h e

The number o f z e r o e s a t

i s t h e c o e f f i c i e n t bk of A ( q - k ) i n the f a c t o r i a l form o f t h e l i n e c h r o m i a l P L ( G , A ) Proof. By Theorem 1, e a c h z e r o i n D r e p r e s e n t s a c o l o r p a r t i t i o n of L ( G ) S i n c e t h e p a r t i t i o n v e c t o r s a t l e v e l q-k correspond t o ( q - k ) - p a r t p a r t i t i o n s o f t h e l i n e s o f G , t h e number o f z e r o e s i s t h e number o f ( q - k ) - p a r t c o l o r p a r t i t i o n s of L ( G ) , a t l e v e l q-k t h a t i s , t h e c o e f f i c i e n t bk o f A(q'k) i n L(G) 0 level

of

(9-k)

D

.

.

.

L e t G be a ( p , q ) - g r a p h w i t h p o i n t s Theorem 3 . and l e t L ( G ) be t h e l i n e g r a p h o f G Then i f

.

triangles,

L(G)

contains

= T

T~

.

- iP=o (:i)

...,

v1,v2, v P I G contains T

t r i a n g l e s , where

di

is t h e d e g r e e o f v i Corresponding t o each t r i p l e o f m u t u a l l y a d j a c e n t l i n e s o f G t h e r e i s a t r i p l e of m u t u a l l y a d j a c e n t p o i n t s o f L(G) Three l i n e s o f G a r e m u t u a l l y a d j a c e n t o n l y i f t h e y form a t r i a n g l e i n G o r i f t h e y a r e i n c i d e n t w i t h a common p o i n t of G 0 Proof.

.

.

Theorem 4 . and l e t A

Let

PL(G,A)

...,

be a ( p , q ) - g r a p h w i t h p o i n t s v1,v2, v P' n-1 = C biA(n-i) L e t di d e n o t e t h e d e g r e e o f vi, G

.

i=o

t h e maximum d e g r e e o f

G

, and

T

bi

of

A(n-i)

t h e number o f t r i a n g l e s o f

G.

Then

1.

The c o e f f i c i e n t

c o u n t s t h e number o f

( n - i ) - p a r t c o l o r p a r t i t i o n s of t h e l i n e s o f 3.

n = q , t h e number of l i n e s o f I f br # 0 , t h e n r s q-A

4.

bl = (q2 )

5.

b2 =

2.

Proof.

1.

-

[ti] . [ti)

.

i=l

i=l

+

G

-

bl[";')

,

G.

and

bo = 1.

.

~(q~q-2)

The number o f A-colorings a s s o c i a t e d w i t h e a c h ( n - i ) - p a r t

.

Hence bi , t h e c o e f f i c i e n t c o l o r p a r t i t i o n of L ( G ) i s A ( " - ~ ) of A ( n - i ) , c o u n t s t h e number of ( n - i ) - p a r t c o l o r p a r t i t i o n s of L ( G ) . 2 . The unique c o l o r p a r t i t i o n o f L(G) w i t h t h e g r e a t e s t number of p a r t s i s t h a t i n which e a c h l i n e i s a c o l o r c l a s s . Thus c o l o r i n g s of L ( G ) a s s o c i a t e d a = 1 0 3 . The s m a l l e s t number o f c o l o r c l a s s e s i n a c o l o r p a r t i t i o n o f L ( G ) i s x' , t h e l i n e c h r o m a t i c number o f G , so e v e r y

t h e r e a r e q c o l o r c l a s s e s and A ( q ) w i t h t h i s p a r t i t i o n , so n = q , and

.

19

Line graphs and their chromatic polynomials

color partition has at least X I color classes. Since, by Vizing's Theorem, x' = A or x' = A+l , if br # 0 , then q-r ;r A or q-r 2 A + l Hence r 5 q - A 1 s q - A , so r s q A 4. Let B = Cl,bllb21...lbr,0,0,...101 be the coefficient vector of PL(G,X), the line chromial of G expressed in factorial form, and C = ~1,c1,c2,...,c 1 the coefficient vector of PL(G,X) 9-1 expressed in standard form. Since Bas1 = C , we get 1 9 B u t since s(q,q-1) = -(;) and l*s(q,q-l) + bl*s(q-l,q-l) = c1

-

.

-

.

.

Again from the fact that Basllq= c , we get 5. l*~(q,q-2)+ bl*s(q-l,q-2) + b2.s(q-2,q-2) = c2 . But ~ ( q - l ~ q - 2 ) =

(q;l)

Hence

,

s (q,q-2)

[ZL) - ' -

b2 =

Example 2.

= 1

+

,

~ ( q - 2 ~ q - 2=) 1

1 2(3)

-

+

bl Cq;l)

' ]

P di i=l [ 3

and it is known that

+

b2 = [ZL)

bl(q;l)

-

-

T

-

2

(3)

7 = (2)

-

+

1

2

+

4 3(2)

-

[zL]-

TL =

so

.

~(q~q-2)

3 2(3) = 1 + 0 + 0 + 2 = 3.

-

:p),

i=l

From Example 1, we know that if

+

c2 =

0

G =

Therefore

.

35 = 1

References C11 Bari, R.A., and Hall, D . W . , Chromatic Polynomials and Whitney's Broken Circuits, J. Graph Theory 1 (19771, 269-275. c21 Harary,~., Graph Theory, Addison Wesley, Reading, 1969. C31 O'Connor,M.G., A Matrix Approach to Graph Coloring, Honors Thesis , Mt .Holyoke College (1980) C41 Riordon,J., An Introduction to Combinatorial Analysis,Wiley, New York, 1967.

.

20

R.A. Ban' APPENDIX Chromials and L i n e Chromials o f Connected Graphs w i t h a t most F i v e P o i n t s and E i g h t L i n e s I n t h e following t a b l e , t h e c o e f f i c i e n t v e c t o r s of t h e f a c t o r i a l

form of

P(G,A)

(p,q)-graph with

and p

a r e given f o r each connected

PL(G,A) 5

5

and

0

q s 8

.

C1,Ol

c11

C 1 , l ,Ol

c1,01

c1,0,01

c1,0,01

C1,3,1 to1

c1,1,01

C1,3,1,01

c1,0,01

c1,2,0,01

C 1 , l ,O,Ol

c 1 , 2,1,01

c1,2,1,01

c1,1,0,01

c1,2,1,0,01

c1,0,0,01

[1,3,3,1,0,01

C1,6,7,1,01

c1,0,0,01

C1,6,7,1,01

C1,3,1,01

C1,6,7,1,01

c1,2,0,01

C1,5,4,0,01

C1,3,1,0,01

C1,5,5,4,01

C1,4,3,0,01

C1,5,4,0,01

C1,4,2,0,01

C1,5,4,0,01

c1,2,0,0,01

Line grapk and their chromatic poiynomiuls

C 1,5,1,0,01 c1.5,4 , O f 0 1 C1,4,3,0,0,01 C1,6,8,1,0,01 C1,6,9,2,0,01 ri,5,5,i,o,oi

C 1,7,12,1,0,0,01 ri,6,9,2,0,0,01 C1,6,9,4,0,0,01

C 1,0,17,8,0,0, 01 c1,9,23,17,2,0,0,01 c1,10,29,25,2,0,0,01

21