y=4 6.1. Introduction In graph theory, graph coloring is a labeling. It is an assignment of labels, colors, to elements of a graph subject to vertex coloring assigns a color to each that no two adjacent vertices have the special case , traditionally Wy call certain constraints t raph sug, Of graph, ‘The starting point of graph coloring i other coloring problems can be transfa version. For example, ise vertex coloring as graph presents an edge of G and agate ae i ige of G and-a pair of whose parties are adjacent if and only ithe corresponding edges i lanar geagnmon end point, Also, the dual graph of «cies to cachet, @ i8 graph which has a vertex eorrccpouiig gach plane region of G, and an edge joining the vertices i regions for each edge in G, fort representing two neighborin, certain embedding of G, The convention of usit igi ng colors originates from coloring the countries of a map, where each face is literally colored. T! ‘0 coloring the faces of a planar gral was later generalized GRAPH COLORING Graph coloring can also be viewed For example, suppose we have s vertices of a graph G with k disti nyertices of G into k distinct sets 8 a partitioning problem, tuccessfully painted all the n inet colors. Then we can group of vertices having same color, Graph coloring and partitio problems such as coding theor computers, register allocation j sequential machines, ete ning are applicable to many Partitioning of logic in digital in compilers, state reduction of In this chapter we concentrate mainly on vertex coloring and its several properties. An important aspect of graph coloring is matching. This chapter also deals with the theory and application of matching problems, 6.2. Vertex Coloring, Chromatic Number Given a graph G, a vertex coloring problem (or in general, a graph coloring problem) is to determine the minimum number of colors required to paint all the vertices of G in such away that no two adjacent vertices have the same color. A painting (or labeling) of all vertices ofa graph G with colors such that no'two adjacent vertices sharing the same edge have the same color is called the proper coloring or simply coloring of the graph G. Since a vertex with a loop can never be properly colored, it is understood that graphs in this context are looples. i jgned a color in which every vertex has been assigne tessa to's yooperclorng's called s properly colored graph. aoe in many different w: A given graph can be properly colore : Fig.6-1 shove three diferent proper colorings ofthe graph G. vertices is small, labels like red, green, Phen the ue ve used. Normally, the colors of labels blue, yellow, ete. can be used. N orm Oe . are drawn from the set of natural hh Gwith at most k colors is called proper coloring ofthe graph @ with at mot proper k-coloring ot simply color a graph G is ‘The emallest number of colors needed to colors EPAP! { jenoted by x(G) Galled ite chromatic number and is denoted by 2( f Fig.6.1(¢) shows that x(G)=2~ ; ti Vie= 458 DISCRETE MATHEMATICg A graph G that can be assigned a proper h-colorin, colorable and G is called k-chromatic Fig6.1 shows that G is 2-chromatic, RG oR a boa ba 6 ¢ 1"! = I6 de d ci) & Y B RI Poole QR, QB « (b) © Legena: {R= Red, G= Green, B= Blue, = Yellow, P= Pink Fig.6.1 is called j. Provided 1(G) =). Jiftbset of vertices assigned to the same colors called : acolor Clige. Every such clas forms an independent set Thee er ¢ is the same as a partition of the vertex set of the into k independent (dig) joint) sets. Thus the terms k-parti, Jecolorable are synonymous in this context, 1g there is no reason to considerdisconnected 50, because the coloring of vertices of one component of a coloring of the ot investigate col regarded. Thus in agraph coloring ‘we need to consider only simple connected graphs. Important Observations + Anll graph (ic. a graph containing isolated vertices only) is monochromatic, ie., 7(G)=1, + A:simple connected graph G containing one or more edges is at least bichromatic, i.e., (G) 22. + Fora complete graph K, with n vertices, a(Ky)=" since all its vertices are ai cent to each other. It follows that a graph containing a complete graph of problem, 459° ices is at least. r- chromatic. For oxample, all ale is Ky . Soa graph containing’a triangle is trian eee g at least 3-chromatic. If G be a graph having n vertices then MG)sns Let Hbe a subgraph ofthe graph G. Then xs x(G)- > ca If deg(v) =¢ then at most d colors are required to co all the vertices adjacent to v. ; Every k-chromatic graph has at least k vertices v such that deg(v) 2k-1. Theorem 61 Every tree with two or more vertices is 2- chromatic. i let v be the root . Let Tbe a tree. If Tis a rooted tree, Grea, If Tis not a rooted tree, let uv be a leaf node Fie.6.200)). @ -to) Fig. 6.2 Proper Coloring of Trees i i t to v with, Paint v with color 1. Paint all the vertices adjacent to v w: color 2. Next paint the vertices adjacent to these vertices (i.e., the vertices that i ith color been colored with color 2) with col rgcees of painting till all the vertices of Tare i \teven distances Colored. We observe that v and all the vertices at from v are colored with 1, while all the vertices at odd distances from v are colored with 2. GNpr iso, along any path of Tthe vertices are ofalternat Since there is one and only one path between ar ofa tree, no two adjacent vertices have T has been properly colored with a mi Since Thas at least two Hence, ic., Tis 2.chro DISCRETE MATHEMATIC, ing colors, 1e same colo) imum of two colors, vertices, it can not be monochromatic, matic, (Proved.) Note 2, The converse of the above theorem is not tr rue. That is, in general, every 2-chrom: graph may not be a tree, For cxample, a bipartite graph is 2-chromatie ( though it is not a tree, characterises all 2-chro (Theorem 6,5) See Fig.6.3. However, Theorem 6,3 ‘matic erao} Fig. 6.3 Proper coloring of bipartite graph n(2 3) vertices is 2-chromatic ifn is even and 3-chromatic if n is odd, Proof. Recall that C, isa graph with n vertices consisting ofa single circuit involvin i all its vertices Let us label the vertices of C, with numbers 1, 2, 3, ou. min Sequence. We then assign color 1 to the vertices labelled with odd numbers and color 2 to the vertices labelled with even numbers, If is even, then no adjacent vertices will have the same color (see Fig.6.4(a)). If n is odd, then the n-th vertex and the first vertex will be adjacent and they will have same color. Thus if n is odd, a third color is needed for proper color: ing (sce Fig.6.4(b)). ‘Thus, _[2 if nis even x6,)-{2 if nis odd Hence proved. Ly tWo Vertices r. Hence ae 461 apt COLORING of aa) Wa, 803) £2) e() (ay c yb ae! eq) Meo Fay d@ Fig. 6.4 Proper Coloring of cycles Cg and C; (Figures within parentheses indicate color numbers) em 6.8. A connected graph with at least one edge is 2- remyatie rand only if it has no circuit of odd length, Proof. Let G be a connected graph having circuits of even lengths only. Consider a spanning tree T of G. Then, Tis 2- chromatic (Theorem 6.2). i ven in the proof of Theorem the coloring procedure given in tl ba lvus paint all he vertices of Testh two coor, For every chord, paint the end vertices not in T’ with color 2 (olor 1 i the other end vertex of it (which is in 7’) has color 1 e lor 2). Sno circuit of odd length, the end vertices of every Shon edd to I ave ilereniycsloeds Thus O i properly colored with’a thinimum of 2 colors. It follows that z(G)=2. i rh, then by Conversely, if G has at least one circuit of odd length, Theorem €2 wt would neod a ninimum of three colors (at least for that circuit) to properly, color G. Consequently in t case x(G)23. . Hence the theorem. Theorem 6.4. If 4(@) be the maximus of the graph G, then 7(G) <1+A(G) Proof. Let nbe the number of vertices of theorem by the method of induction on degree of the vertices We shall prove the e G with n verti- Consi ition P(n): “ For a graph ¢ ’ cen (@) se BUG) where n(el) isa postive integer’ For n=1, 4(@)=0 and 2(G)=1. +. PQ) is true.We assume that Pim) is true for some positi Positive integor This means that fora graph Gwithm vortices 1G) st ave Nog et G be a graph having m+1 vertices, Let be a vers, b ; aver ofGand G'=G™ {0} be theraphobinn a ht Gy deleting the vertex v and all the edges incident with it . Then a(G)< a(@) Now G" can be props ¢ erly colored with 7(G’) colors, Since G' has m vertices, by the induction hypotl c he 2G’) <1+AG) = 7G’) 51+ AiG) by (1). Tr ‘Thus G" can be properly colored with at most 1+A(G) colors, Since there are at most A(G) vertices adjacent to v, i that one of (1+.A(G)) co (G) vertices adjacent to v, it follows lors can be used to paint v. ‘Thus G can be colored with at most (1 immediately that P(m_+1) is true w! PA) is true. Hence by the Pri tion P(n) is true for all positive Hence the theorem. +4(Q)) colors. It follows jenever P(m) iple of Mathematical Indue- itegral values of n>1, Theorem 6.5. Every bipartite graph with at least one edge is 2-chromatic and conversely. Proof. A graph G is called ipartite if its vertex set V.can be decomposed into two disjoint subsets V, and Vp such that every edge in G joins a vertex in V witha vertex in V2. Obviously a bipartite graph cannot have any self-loop. Also a set of parallel edges, ifany, between a pair of vertices of G can all be replaced by only one edge without affecting the bipartiteness of the graph G. If the bipartite graph G has at least one edge, it cannot be monochromatic. So 7(G)2 2. Now we can paint each vertex of Yj with color 1 and each vertex of Vz with color 2. Then G will be properly colored with a minimum of two colors. Thus 7(G)= 2. Conversely, let G be a 2-chromatic graph. Then the coloring of G partitions the vertex set Vof G into two disjoint subsets V1 oy part COLORING 1s sr such that no two vertices of V; (or Vp) are adjacent, Ay definition G is a bipartite graph. once the theorem. 4. The consequence of Theorem 6.1, Theorem 6.3 and Theorem Nase 15. the [ollowing theorem. at least one edge is 2-chromatic Agraph G 2 aaepinareapeh ing conditions is satisfied: ifand only if one of the fo (a) Gisa tree. (&) Every cycle of G has even length. (© Gis bipartite graph. | ] Note 4. Gem ig the concept of bipartite graph, we can define p»partite graph as follows: A graph Gis called p-partitegraphif it vetexset Veanbe decomposed into p disjoint subsets fp that no edge in Goins the verties inthe sane subset but joins the vertices in distinet subsets. Clearly, a k-chromatie graph isp-pai Note 5. All the theorems on 2-chromatic graphs can be safely ex- tended to k-chromatic graphs for k > 2. if and only if ks p- 6.3, Edge Coloring and Total Coloring 6.3.1. Edge coloring i An edge coloring of a graph Gis a proper coloring of ts edges, ie., it is an assignment of colors to edges, aa pa vertex of G is incident to two edges of the same color. Fig.6.5(a) for illustration. ati ego coloring with k colors is called heedge-coloring equivalent to the problem of partitioning the matchings. Fig.6.5(a) shows a 3-edge col ae ‘Tho smallest number of colors needed fo an oe atl fe is -hromatic index or y ‘raph Gis called cl nagar) 210)" ber and is denoted by 2'(G)- In Figspe DISCRETE MATHEMATICS A Tait coloring is a 3-cdge coloring of a cubie graph (i regular graph ). See Fig.6.5(). 6.3.2. Total coloring A total coloring vertices and edges, as well as to edges. A Proper in the sense that with its end vertices a forillnetratinn ofa graph G is a proper coloring of all its » itis an assignment of Colors to vertices total coloring is always assumed to be {tno adjacent vertices and no edge along re assigned the same color. See Fig.6.5(c) (c) Fig. 6.5 (a) Edge coloring (b) Tait coloring (c) Total coloring The least number of colors needed for total coloring of a graph Gis called the total chromatic number of G and is denoted by 7G). It can be easily verified from Fig.6.5(c) that 7O=5. nf COLORING 465 e Ee Independence and Chromatic Pa 64 : wn that a proper coloring ofa graph Jn Section 6.2 a Sf the set of ite vertices into distinct and uces & Pe. For example, in Fig.6.1(c), we see that coloring Aiea a etaree partitionings {04}p.¢- {22% Ysloneq, and 1G Pros wo vertices belonging to any of these three subsets (bay ent. Such a subset of the set of vertices of a graph is 2 atin independent set whose formal definition is as follows. al ices i is said to be an independent set of A eee ee ndependent oot oran internally stable ices i jacent. For example, the ifno two vertices in the set are adjacent. A aes ay is an independent set of the graph G in Fig.6.6. ty = Fig. 6.6 Asingle vertex in any graph forms an independent set. ‘An independent set of a graph G to which no other vertex of G can be added without destroying its independence property is called a maximal independent set or maximal internally stable set of G. For the graph G in Fig.6.6, the set {u.v,,0;,05} is an maximal independent set. The set {0,,0,,0,,u,} is another maximal independent set of G. Thus itis clear that a graph may have more than one maximal independent set of different sizes. ‘The number of vertices in the largest independent set ofa graph Gis called the independence number or coefficient of internal stability of G and is denoted by f(G). 80 tionMA v 466 DISCRETE MATHEMATICS, Given a simple connected graph G, the chromatic Partition, ing of G is the process of dividing the vertex set of G into the smallest possible number of disjoint independent sets, Theorem 6. B(G)z : 1£G bea k-chromatic graph with n vertices thon fore, all the n vertices of G are properly colored with b cola Since the largest number of vertices cannot exceed the independence mm k distinct colors in the coloring, sin G with the same color umber (G) and there are ‘we must have kB(G)zn = p(G)22. Hence proved t Tesorem 6.8. Let P 2(G)=|P| where In other words, al be a partitioning of the graph G. Then is the number of independent sets in P. |P|-chrom: Proof. From the definition of the independent set, it follows that one color is needed for each independent set for proper coloring of the graph G. Since in any chromatic partition P of G the independent sets are disjoint while their union gives the vertex set of G, therefore, minimum colors needed for proper coloring of Gis |P|. Hence z(G)=|P|. Consequently, G is |P|- chromatic. (Proved) 4.1. Procedure for Finding Maximal Independent Set ‘The method which we are going to describe is based on Boolean arithmetic. Let G = (V,£) be a simple connected graph. Let each vertex of the vertex set V={u,ty,.....,, } be treated u. a Boolean variable. We define the Boolean operations of adn multiplication (.) and complementation (') as follow: © — Wu, €V, oj +0; = operation of including either vertex vu; or vertex Ujor both, aa yr COLORING 467 1%) both the vertices v,and v;. eV, uf = operation of excluding the vertex v,. we ¥ aximal it in find mal independent set for G, we require to fi fo boot of V that does not include the two end vertices maxi any edge in E. i ts end vertices, is completely characterised by it a om edge (y;,u,)e£ as a Boolean product 4.0) ero », are the end vertices of the edge. here % thus“including all edges” means the sum of all products (SOP ipe UU; Now we follow the steps as given below. Step 0: Start :Form the Boolean expression x ‘eV ve yy x Step 2:'Take the complement y’ of y and express it as a sum of products as follows. Va At htt hy (Bmploy De Morgan's Law and the following identities: (i) aa =a.fia+a=a (jii)a+ab=a a, ieee aera ep 0: Th ber of terms in y’ is the number of maximal ependent ects of Exclude fom the vertex set V, the tices appearing in fj in the complemented form. This give th maximal independent sot. Step 4: Stop. AVertex set is a maximal independent set © y=0 (logically false) © y'=1 (logically true)© atleast one fj =1 ‘© each vertex appearing in fj excluded from V. Thus each f, will produce a maximal independent, sot and ever maximal independent set will be produced by this meth Finding Independence Number % After finding all the maximal independent sets of G, determing the size of that set which contains the largest number of vert, ‘This gives the independence number (G) of G. 7 Finding the Chromatic Number role Hee Ue) (ra eas 0406) "geile oe Fe the in complemented form ig After finding all the maximal independent sets of G, determine the minimum number of those sets whose union is the verieg set V. This minimum number of set: number 7(G). cluding fom V the vertices appearing in each term in comple- ented form in y* we get the following six maximal indepen- dent sets: (resets (rere) (rr ees te} {er eaves}, fee, ee} and {us}. ‘The size of the maximal independent set having largest num- ber of vertices is 3. Independence number of G, A(G)=3. ‘The minimum number of the above maximal independent sets, ‘hich collectively include all the vertices of G is 3. (Since {01104 ve} U{t1 U9, 46} {Re Ho = V {u, 04, ug} Us, U5} U {vg} = V, a minimum of three sets satisfy the condition.) Finding Chromatic Partitioning After-enumerating all maximal independent sets, smallest number of disjoint sets that include a the graph. This constitutes a. part Partitionings of a given graph Ga class of maximal select the he vertices of ioning of G. Several distinet re possible depending on the dependent sets of G. Illustration Consider the graph G=(V,£) in Fig.6.7 where V = {01s Ups Uys U4, Us Up} - Expressing each edge as a Boolean product of ite end vertioos and considering all the edges we form the expression Y= UU + Us + Und + Uns + UyUy +UGUS 4" = (vj #Uh)( Ue +05) (ve +04) (4 +05) (05 +04 )(05 +06) [by De Morgan's Lavs] , a +ab =a, a, b being (G)=3, Five chromatic partitionings of G obtained from the above aximal independent sets are les 86) (eas 0 )s ea) {ates Yo) (ate) (4.05.45) (Ou Yo) (ea)fs {Cer Pa Ye)» (Mes %5)o (and (4.04), (eye 05)» (02s eo) ied. Employing the rules aa=a, a +a boolean variables, we get; 71 ig 470 y eV and yj e\ Now any induced subgraph of the bipartite graph Gis either a null graph or a bipartite graph. Since the clique of a null graph does not exist, we do not consider it. 1 iparti ic it dge, is of order 1 bipartite graph every clique, being an edge, is’ two. It follows that the clique number of every bipartite graph is 2, Further a minimum of two colors is needed to properly color a bipartite graph. it implies that the chromatic number of any bipartite graph is 2:ln other worde, if G is 2 bipartite graph then 2(G)=2=0(4). Tt follows immediately that any induced sub; Staph has same chrom: €very bipartite graph isa perfect graph. (Proved)P's Us - Wri gp tort G: edeawn, eo Redeem, 3 Be v a 1g. 6.10 Problem 5. Find four indepe Pendent sets, independence nu: the following graph G. Also fin uber and chroma\ ¢ t Fig. 6.16 Solution. Given graph is G=(V,E) V=(a,hed¢f,g. Four independent set “of G are face}, {a,c,f},{c,f,e} and {a,c,¢, 8} Expressing each edge as a Boolean product of its end vertices and considering all the edges of G we -form the following ex- pression. y=ab+ad+ed +de+dg+df+ ig DISORETE MATHEMATIC Aent sets, all maximal inde- number of \d chromatic partitioning of G, COLORING 479 ————$$______"" spine emplements and using De Morgan’s law we get pelo sB\(a' +a) +a) d'seV(a'+ a (aes y(r+e') sploying the rules aa=a, a+a=a,a+ab =o, a, b being ean variables, we get yo(ata +a'b'+bid')(ed's ce’ +a’ +e) (@+af'+ed'+e7\(f'+8') a(o+bad)\(d'+ce)(a'+eF\(f' +8’) a(od'+b'd'sa'ce' +b'dce)(af'+d's'+ ef’) a(o'd' +b'd'+a'ce)(df'+d's'+ 2/7’) cddf'+ald'g' +a'd'gy'+bafsbdg sba'gf ta'ced'f'+a'ce'd'g'+a'c'e'g'f' sadf'+a'd'g'+bdf'+bd'g' +a'cegy’. Excluding from V the vertices appearing in each term in comple- mented form in y’ we get the following five maximal indepen- dent sets: {b, c,¢, gh, {beef}, {ocre 8}, (2,66, f} and {b,d}. (Ans) The size of the maximal independent set having largest num- ber of vertices is 4. So the indepnedence number of G is A(G)=3. (Ans.) The minimum number of above maximal independent sets which collectively include all the vertices of G is 3. (Exz.,{b, c,¢, F}U{a,¢,€, }U{b, d} =V, ete.) Hence the chro- matic number of the graph Gis 7(G)=3. (Ans.) Only two chromatic ». ttitioning of G exists. These are {eee,2).(6,4)} and {(a,e.6,/),(b4)}. (Ans)Fig. 6.17 & 2. Find the edge-chromati = atic number and total ber of each of the graph Gin Figen & Find all the cliques, maxima cues, clique number and intersection numbe Goffige.17, ee £. maximum cliques, r of each ofthe graph 4. Show that the following graphs are perfect, Fig. 6.18 5. Find four independent sets, all maximal independent sets, independence number and chromatic number of the following graph G. Also find chromatic partitioning of G. maticnum Fig. 6.19 Answers 1. x)= 4 1s. 1(G)=5. 2"(G)=6. 3. Cliques of G: {a,b g}, {a,b e}, {a,¢, g}, {eg}, {b..d}, {bd g}, {bed}, {eed}, {deg}. Maximal cliques of G: {a, b, g}, {a,,e}, {a, erg}, (6,¢, 4} {d, f, a}. {-d,¢, 8} - Maximum cliques of G: {b, d, ¢, €}- o(G)=4, Intersection number of G is 3. §, Maximal independent sets : (tity, U4, U6}s {040 UG U4, Ur}s Ua, Ufo (Cre Ug}- A@=4, G)=3. somatic partitioning : {(%, U3» U4» Yo)» (ve %):(%s)}, {Cee Garey), (ear ve) (sdf {Cees 84 Ya) (ede ere (i Ys)}> tte, 68, Chromatic Polynomial A graph G having n vertices can be properly colored in many. different ways using a large number of colors. The number of different 2 -colorings (ie., coloring using 2 cr fewer colors) of riven graph G can be expressed by racuns of a function in 2 tua is dencted by chr(G, 2)iG 483 D . Ay encom a —— ic Polynomial chrome £), where |V|=n. Having established the above et a- (Vi chil the function chr(G, A) as the chromatic poly- sao degree n of the graph G and denote it conveniently x (A) + ashy us determine the expression for P,(2). et a be the diferent ways of proper coloring of G using ex lat ¢ Pe forent colors. Now r colors can be chosen out of 4 acy aE) different ways. (C(2, r)denotes combination color stinct things out of 2. distinct things.) a can be properly colored using exactly r colors out of 2 abr in c, xC(4,r) different ways. The value of chr(G, 4) gives the number of ways G ¢ Properly colored with 4 or fewer colors. Theorem 6,9. (@) chr(G, 2) isa polynomial in 2. () chr(G, 2) is of degree n where n is the num! vertices of the graph G. Proof. (@) For any coloring of G, the nonempty color classes constitute 4 partition of the vertex set Vof G where each part is a stable Now it is not possible to use more than n colors to paint n ver- 0 tices. It follows that 1 () We have G=(V,£), where |V|=n.Following part (a), we observe that there is no partition of G with more than n parts and there is only a single partition with exactly n parts this partition, the number of colorings is a polynomial of d n while for all other partitions it has a degree less than sum of all such polynomials is a polynomial of degree n. Hence proved.486 DISCRETE. MATHEM, TICs can be painted in (4-2) different ways, ... and finally ¢ e n-th vertex of it can be painted in (4-n+1) different Ways, Hence by the product rule of counting we get P(aj= 4(a~1)(A-2). .. (A-n+1) which is the Necessary as well as sufficient condition for a graph with n vertices tobe a complete graph. (Proved) Theoreny£1 polynomial 2. Any tree T, with n vertices has chromatic P(a)=A(A-1)"". Proof. Let T, be a tree with n vertices. To prove th We apply induction on n, which than zero. theorem, is a positive integer greater For n= 1, T, has only one vertex which cai different colors in 2 different ways. Also, PB(A)= 2) true for n = 1, n be painted with 1 (4-1)" =. Therefore, the given statement is Let us assume that the given statement is integer m21, Then for the tree T’, with m vertices, we have P,(a)=a(a-1)"" ws (1) Consider that tree Th With (m+1) vertices. We select a leat node, say v, and delete it from Tat true for some positive The resulting garph remains a tree with m vertices. Hence by the inductio: n hypothesis its chromatic polynomial is A(a-1)" This means that all the m vertices of the tree can be colored in 4(A-1)"" distinct ways. Then the selected leaf node v can be assigned with any of the 4 colors except that of its neighbours in (4-1) different ways. Hence by the product rule of counting, Fa (A= A(A~1)" x(a -1)=a(a-1)"™ Thus the given statement is true for n=m-+1 if it is true fo n=m. But the statement is true for n=1. Then by the Principle of Mathematical Induction, the given statement is true for all integral values of n21.488 DISCRETE MATHEMAri¢g Theorem 6.12/The chromatic polynomial of a length nis P.(a)=(A-1)" +(-1)"(2-1). Proof. The cycle ©, of length n has n vertices where apply induction on n. ny cycle C. of N23. We For n=3,C, becomes K,. Then by Theorem 6.1 0, chromati polynomial of C, = 2(4-1)(4-2) mati Also from the given statement R@=(4-1) +C1)(4-1) =(4-1)(2 ~PA+1-1)=A(A-1)(2~2), . The given statement is true for n= 3. Let us assume that the given statementiis true for some positive integer m23. ‘Then for any cycle of length m, P,A=(2-1)" +(-" (4-1) ~ ff Let us consider the cycle C,.,, of length (m +1). We delete an edge from the cycle C,,,. Since deletion of an ‘edge from a cycle does not alter the number of vertices in the cycle, the graph is a path, which is actually a tree with (m+ vertites. ‘Therfore, its chromatic polynomial is 4(2-1)" (by Theorem 6.11). Again contracting an edge from C,,. yields a cycle of len , which by inductive hypothesis has a chromatic poly (4-1)" +C1)"(4-1)- 2. By deletion-contraction property of chromatic polynomial, the chromatic polynomial for C, =A(a-1)" -{(@a-ay" c (2-1) =(4-1)"(4-1)- Cay" (4-1) =(4-1)"" + (a-1) GRAPH COLORING An FFs i i =m-+1 whenever it is Tae the en given eatement ia tre for n=, Hence by the Principle of Mathematicsl Induction the given state- mont is true for all positive integral values of n 2 3. / «. The chromatic polynomial of any cycle C, of length n is Pya)=(4-1)" +E)" (2-1). Proved) Illustrative Examples 2 Problem 1. Find the chromatic polynomials of the follow- ing graphs. Solution linding the chi ‘The given graph is G, =(V4, B,) where Vj = {uy,vp.ty, U4, U5) - Since |Vj| =, the chromatic polynomial P,(2) of G, is of 5-th degree. x aa [ foo G0 [2B 2 a +o[ne ae) +q[ Aenea (a ea Since G, contains cliques of order 3 (e., triangles), therefore, atleast three distinct colors are needed to properly paint them, 280, =¢q =0. Also ¢y =5!=120,Pe DISCRETE MATHEMATICg Let us now find cs. We observe that three different colors can be assigned to the clique Vertices, say {v,, 05,04}, in 3! = 6 different ways. Having done this, we have choices for 1, because v, must be assigned the color of vy oF of vy. No choice is left for us, because it must be assigned che cologot &. Thus € =6x2=12, Tofind cy, we have to assign four diferent colors to five verti- ces. We first assign @different colors out of 4 colors tothe clique » ¥3> &4} This ean be done in (4, 3)=4!~ 24 diffe, ‘The fourth color can be assi igned to u or us in 2 ways. The fifth vertex provides no add ional choice, cy =24x2=48 Substituting the values of the coefficients in P(A) we get )=24(4-1)(4-2)+2a(4-1)(4-2)(a-2) +4(4-1)(2-2)(2~3)(4~4) on, PyA)=A(A-1)(4~2)(22-52+8) which is the required chromatic polynomial for the graph G, (Ans.) Finding the chromatic ial for G,: The given graph is Gz = (Vp, Ep) whore V> =v, vy, U9, v4 Since |p| =5, the chromatic polynomial P,(A) of G, is of 5-th degree. nolo) ge 1! 3! +¢ 4 4! BI jy has a clic 'U;, Up, Ug, Uy} of order 4 and this is the maxi- im on ea four distinct, colors’are needed for its proper coloring. eee vq[ Aenea a14-0) f 491 ‘qRAPH COLORING —$@ @-@-@-@_— 4-0) =%9= 0. Also E ct colors to four clique vertices sign four distinct colors to oes a iiresiiBe done in A dtferent waye, Since x SP Vesscebladjacent t0 0, the color of either PERRI et te dasigtied'to 0. So there axe two choices for 4 Sitar color assignment of four colors to v), vty, 0. wap neg =4}x2= 48. ipstituting the values of the coefficients in P,(2) we get Sul t One = 24(4-1)(A-2)(4-8) + A(4-1)(4-2)(2-3)(2-4) a 4(4-1)(4-2)*(4-8) which is the required chro- eae peal Merdeos Gy. Ans.) Problem 2. Find the chromatic polynomial for Ky.» Solution. Ko. is the complete bipartite graph having 5 vertices. Fig.6.22 shows K2,3. hai tg. Fig. 622 ; ne Here the vertex set is V = {uy, v», vy, vy, Us}. Since |V|=5, chromatic polynomial P(2) for K.s is of 5-th degree. voltages] +9[ {nes eM ‘The graph has cliques of order 2. So at least two colors are ‘needed to properly paint them. A(a-1)(A-2)(4-3)(4=4) 3!