Study of Lattice Modules and Related Topological Aspect

If the vertices of a graph represent radio stations, and two vertices are adjacent if the stations are close enough to interfere with each other, a coloring can be used to assign non-interfering frequencies to the stations. If the vertices of a graph represent traffic signals at an intersection, and two vertices are adjacent if the corresponding signals cannot be green at the same time, a coloring can be used to designate sets of signals than can be green at the same time. Graph coloring is closely related to the concept of an independent set.A set SS of vertices in a graph is independent if no two vertices of SS are adjacent. If a graph is properly colored, the vertices that are assigned a particular color form an independent set. Given a graph GG it is easy to find a proper coloring: give every vertex a different color. Clearly the interesting quantity is the minimum number of colors required for a coloring. It is also easy to find independent sets: just pick vertices that are mutually non-adjacent. A single vertex set, for example, is independent, and usually finding larger independent sets is easy. The interesting quantity is the maximum size of an independent set.

number of GG is the maximum size of an independent set; it is denoted α(G)α(G). The natural first question about these graphical parameters is: how small or large can they be in a graph GG with nn vertices. It is easy to see that 11≤χ(G)≤n≤α(G)≤n1≤χ(G)≤n1≤α(G)≤n and that the limits are all attainable: A graph with no edges has chromatic number 1 and independence number nn, while a complete graph has chromatic number nn and independence number 1. These inequalities are thus not very interesting. We will see some that are more interesting. Any coloring of GG provides a proper coloring of HH, simply by assigning the same colors to vertices of HH that they have in GG. This means that HH can be colored with χ(G)χ(G) colors, perhaps even fewer, which is exactly what we want. Often this fact is interesting "in reverse''. For example, if GG has a subgraph HH that is a complete graph KmKm, then χ(H)=mχ(H)=m and so χ(G)≥mχ(G)≥m. A subgraph of GG that is a complete graph is called a clique, and there is an associated graphical parameter. The clique number of a graph GG is the largest mm such that KmKm is a sub-graph of GG. It is tempting to speculate that the only way a graph GG could require mm colors is by having such a subgraph. This is false; graphs can have high chromatic number while having low clique number; see figure 1. It is easy to see that this graph has χ≥3χ≥3, because there are many 3-cliques in the graph. In general it can be difficult to show that a graph cannot be colored with a given number of colors, but in this case it is easy to see that the graph cannot in fact be colored with three colors, because so much is "forced''. Suppose the graph can be colored with 3 colors. Starting at the left if vertex v1v1 gets color 1, then v2v2 and v3v3 must be colored 2 and 3, and vertex v4v4 must be color 1. Continuing, v10v10 must be color 1, but this is not allowed, so χ>3χ>3. On the other hand, since v10v10 can be colored 4, we see χ=4χ=4. Bipartite graphs with at least one edge have chromatic number 2, since the two parts are each independent sets and can be colored with a single color. Conversely, if a graph can be 2-colored, it is bipartite, since all edges connect vertices of different colors. This means it is easy to identify bipartite graphs: Color any vertex with color 1; color its neighbors color 2; continuing in this way will or will not successfully color the whole graph with 2 colors. If it fails, the graph cannot be 2-colored, since all choices for vertex colors are forced.

If a graph is properly colored, then each color class (a color class is the set of all vertices of a single color) is an independent set.

Proof We show that we can always color GG with Δ+1Δ+1 colors by a simple greedy algorithm: Pick a vertex vnvn, and list the vertices of GG as v1,v2,…,vnv1,v2,…,vn so that if i

There are graphs for which χ=Δ+1χ=Δ+1: any cycle of odd length has Δ=2Δ=2 and χ=3χ=3, and KnKn has Δ=n−1Δ=n−1 and χ=nχ=n. Of course, these are regular graphs. It turns out that these are the only examples, that is, if GG is not an odd cycle or a complete graph, then χ(G)≤Δ(G)χ(G)≤Δ(G).

The greedy algorithm will not always color a graph with the smallest possible number of colors. Figure 2 shows a graph with chromatic number 3, but the greedy algorithm uses 4 colors if the vertices are ordered as shown. In general, it is difficult to compute χ(G)χ(G), that is, it takes a large amount of computation, but there is a simple algorithm for graph coloring that is not fast. Suppose that vv and ww are non-adjacent vertices in GG. Denote by G+{v,w}=G+eG+{v,w} = G+e the graph formed by adding edge e = {v,w}e = {v,w} to GG. Denote by G/eG/e the graph in which vv and ww are "identified'', that is, vv and ww are replaced by a single vertex xx adjacent to all neighbors of vv and ww. (But

single edge from xx to uu in G/eG/e.)

Consider a proper coloring of GG in which vv and ww are different colors; then this is a proper coloring of G+eG+e as well. Also, any proper coloring of G+eG+e is a proper coloring of GG in which vv and ww have different colors. So a coloring of G+eG+e with the smallest possible number of colors is a best coloring of GG in which vv and ww have different colors, that is, χ(G+e)χ(G+e) is the smallest number of colors needed to color GG so that vv and ww have different colors. If GG is properly colored and vv and ww have the same color, then this gives a proper coloring of G/eG/e, by coloring xx in G/eG/e with the same color used for vv and ww in GG. Also, if G/eG/e is properly colored, this gives a proper coloring of GG in which vv and ww have the same color, namely, the color of xx in G/eG/e. Thus, χ(G/e)χ(G/e) is the smallest number of colors needed to properly color GG so that vv and ww are the same color.

The upshot of these observations is that χ (G) = min (χ (G+e), χ (G/e))χ(G) = min (χ (G+e), χ(G/e)). This algorithm can be applied recursively, that is, if G1 = G+eG1 = G+e and G2 = G/eG2 = G/e then χ (G1) = min(χ(G1+e), χ(G1/e))χ(G1) = min(χ(G1+e),χ(G1/e)) and χ (G2) = min (χ (G2+e), χ (G2/e)) χ (G2) = min (χ(G2+e), χ(G2/e)), where of course the edge ee is different in each graph. Continuing in this way, we can eventually compute χ(G)χ(G), provided that eventually we end up with graphs that are "simple'' to color. Roughly speaking, because G/eG/e has fewer vertices, and G+eG+e has more edges, we must eventually end up with a complete graph along all branches of the computation. Whenever we encounter a complete graph Km it has chromatic number mm, so no further computation is required along the corresponding branch.

1. B.D. Acharya, Set-valuations of Graphs and Their Applications, MRI Lecture Notes in Physics, Allahabad. 2. B.D. Acharya (2001). Set-indexers of a graph and set-graceful graphs, Bull. Allahabad Math. Soc., 16, pp. 1-23. 3. B.D. Acharya, Contributions to the Theories of Graphs, Graphoids and Hypergraphs, The Indian Institute of Technology. 4. B.D. Acharya, M. Lasvergnas, Hypergraphs with cyclomatic number zero, triangulated graphs, and an inequality, J. Combin. Theory. B.33, pp. 52-56. 5. C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam. 6. C. Berge, Hypergraphs: Combinatorics of Finite Sets, North-Holland, Amsterdam. 7. M. Buratti, G. Burosch and P.V. Ceccherint (1997). A characterization of hypergraphs which are products of a finite number of edges, Rendiconti di Matematica, Serie VII Volume 17, Roma, pp. 373−385. 8. F. Harary, Graph Theory, AddisonWesley, Reading Massachusetts. 9. E. Sampathkumar and L. Pushpalata, Eulerian Hypergraph (2004). Advanced Studies in Contemporary Mathematics, 8, pp. 115−119. 10. J. Sedlaˇcek, Some properties of magic graphs, in: Graphs, Hypergraphs and Block Systems, Proc. Conf. Held in Zielona Gora, pp. 247-253. 11. M. Sonntag, Hanns-Martin Teichert, Competition hypergraphs, Discrete Applied Mathematics, pp. 324−329.