GRAPH COLORING AND CHROMATIC POLYNOMIAL SEBASTIAN VATTAMATTAM Definition 0.1. Graph Coloring: Assigning colors to the vertices. Definition 0.2. Proper Coloring: Coloring in which adjaceen vertices get different colors. Definition 0.3. Chromatic Number: The number of minimmu colors for a proper coloring.(G) Definition 0.4. Chromatic polynomial: a variable that stands for the number of available colors. P(G, ) -the number of possible proper coloring of the graph G with colors. It is a polynomial called the Chromatic polynomial. Example 0.1. (1) G = (V,E), |V | = n,E = , P(G, ) = n And (G) = 1 (2) G = Kn, P(G, ) = (n) = (−1)(−2) · · · (−n+1) And (G) = n (3) G = (V,E), V = {v1, v2, ...vn},E = {(vi, vi+1), i = 1, 2, ...n − 1}P(G, ) = (− 1)n−1 And (G) = 2 Theorem 0.5. If graph G consists of the components Gi, i = 1, 2, ...k the P(G, ) = P(G1, ) · P(G2, ) · P(G3, ) · ...P (Gk, )· Definition 0.6. G = (V,E), e = {a, b},Ge = G − e G0e the graph obtained from Ge by coalescing a and b. Date: 16 -03 -10. 12 SEBASTIAN VATTAMATTAM Theorem 0.7. Decomposition Theorem: If G = (V,E) is a connected graph, and e 2 E then P(G, ) = P(Ge, ) − P(G0e, ) Definition 0.8. G = (V,E), a, b 2 V, {a, b} = e /2 E then G+eis the graph obtained by adding e to G. G++ e is the graph obtained from G by coalescing a and b. Theorem 0.9. If G = (V,E) is a connected graph, and e = {a, b} /2 E then P(G, ) = P(G+e, ) + P(G++ e , ) Theorem 0.10. If G = (V,E) is an undirected graph, G1,G2 are subgraphs such that G = G1SG2,G1TG2 = Kn, then P(G, ) = P(G1, ) · P(G2, ) (n) Example 0.2. Consider the graph G = (V,E), V = {A,B,C,D},E = {(A,B), (A,C), (A,D), (B,C), (C,D)} G is the union of G1 = (V1,E1), V1 = {A,B,C},E1 = {(A,B), (A,C), (B,C)} and G2 = (V2,E2), V2 = {A,D,C},E2 = {(A,D), (A,C), (D,C)} G1 = K3,G2 = K3, and G1\G2 = K2 Therefore, P(G, ) = P(G1, ).P (G2, ) (2) = (3).(3) (2) = (−1)(−2)2 Example 0.3. Consider the graph G = (V,E), V = {A,B,C,D,E, F},E = {(A,B), (A,C), (B,C), (B,D), (B,E), See Figure 1 Let us, for convenience, denote the subgraphs of G by the vertex set only.GRAPH COLORING 3 G is the union of G1 = {A,B,C,E} and G2 = {B,D,E, F} G1\G2 = {B,E} = K2 By Example 0.2, P(G1, ) = P(G2, ) = (− 1)(− 2)2 Therefore, P(G, ) = P(G1, ).P (G2, ) (2) == (− 1)(− 2)4 Figure 1. A Map and its Graph4 SEBASTIAN VATTAMATTAM References [1] Ralph P. Grimaldi,Discrete and Combinaorial Mathmatics,Fourth Edition, Pearson Eucation Asia, 1999 Mary Bhavan, Ettumanoor E-mail address: vattamattam@gmail.com