The Coloring of Hyper Graph

The Coloring of Hyper Graph

(1)A. Ramesh Kumar,

1. Head, Department of Mathematics,

Srimad Andavan Arts & Science College, Trichy-05.

(2) G. Kavitha

2. Asst. Professor,

Kongunadu College of Engineering and Technology, Tholurpatti, Thottiam

Abstract: In this paper, we are introducing the Hardness of Hyper-Graph coloring and uniform coloring of the vertices and Kneser Graph KGn,s

MSC Code : 05C65,05C90

1. INTRODUCTION

   A hypergraph H is an ordered pair H (V , E) , where

   V is a nite nonempty set and E is a collection of distinct nonempty subsets of V . H has dimension r if all edges have at most r vertices. If all edges have size exactly r , H is called r -uniform. Thus, a 2-uniform hypergraph is just a graph. A set U V (H ) is called independent if U

   spans no edges of H . The maximal size of an independent se tin H is called the independence number of H and is denoted by (H ) . A k-coloring of H is a mapping

   approach, much in the spirit of coloring algorithm[3] . Not much is known about general approximate coloring algorithms for r -uniform hypergraphs (that is, when the chromatic number of a hypergraph is not given in advance). Recently it presented an approximation algorithm for this problem with performance ratio O(n / log(r 1) n)2 ) , where log (r ) n denotes the r-fold

   iterated logarithm.

   In Section 2 we describe a construction which enables to derive immediately results on hardness of approximating the chromatic number of r-uniform hypergraphs for any r 3 from the corresponding graph results. Thus we get that unless NP ZPP , for any xed r 3 , it is

   impossible to approximate the chromatic number of r – uniform hypergraphs on n vertices in polynomial time

   c :V (H ) 1,……ksuch that no edge of H has all

   within a factor of

   n1

   , for any

   0 . It should be

   vertices of the same color. Equivalently, a k -coloring of H is a partition of the vertex set V (H ) into k independent sets. The chromatic number of H , denoted by

   (H ) is the minimal k , for which H admits a k –

   noted that Hofmeister and Lefmann obtained independently the same hardness result[7].

   In Section 3 we present an approximation algorithm for coloring r-uniform hypergraphs on n vertices, whose

   coloring

   performance guarantee is

   O(n(log log n)2 /(log n)2 ) ,

   In this paper we consider an algorithmic problem of coloring r-uniform hypergraphs, for given and xed value of r 2 . The special case r 2 is relatively well studied and many results have been obtained in both positive and negative directions. .

   NP-hard to determine whether a 3-uniform hypergraph is 2-colorable. Additional results on complexity of hypergraph coloring[1]. These hardness results give rise to attempts of developing algorithms for approximate uniform hypergraph coloring, aiming to use a small but possibly nonoptimal number of colors. The rst nontrivial case of approximately coloring 2-colorable hypergraphs. Both papers arrived independently to practically identical results. They presented an algorithm for coloring a 2-colorable r – uniform hypergraph in O(n11/ r ) colors, using an idea

   closely related to the basic idea [3] . Another result of the above mentioned two papers is an algorithm for coloring 3-

   thus matching the approximation ratio of Wigdersons algorithm[3].

2. HARDNESSOF APPROXIMATION Several results on hardness of calculating exactly the chromatic number of r-uniform hypergraphs have been known previously. It showed that it is NP -complete to

   decide whether a given 3-uniform hypergraph H is 2- colorable]. that it is NP -complete to decide k – colorability of r -uniform hypergraphs for all k , r 3 , even when restricted to linear hypergraphs[2]. A polynomial transformation from k-chromatic graphs to k -chromatic r

   -uniform hypergraphs. Finally, it showed in [4] that, unless P NP , it is impossible to decide in polynomial time 2-colorability of r -uniform hypergraphs for any r 3 .

   However, until recently, there has been no result showing that it is also hard to approximate the chromatic number of

   uniform 2-colorable hypergraphs in

   ~

   O(n

   2 / 9 ) colors. The

   r -uniform hypergraphs, where r 3 . For the graph case

   latter algorithm exploits the semidenite programming

   (r = 2) in[4] , using the result [6] that if NP does not have

   efcient randomized algorithms, then there is no polynomial time algorithm for approximating the chromatic number of an n vertex graph within a factor of

   This is the rst hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k 4 such a result has been shown

   n1

   , for any xed 0 . In this section we present a

   by [14], who also discussed the inherent di erence

   construction for reducing the approximate graph coloring problem to approximate coloring of r -uniform hypergraphs[5], for any r 3 . Let r 3 be a xed

   between the k 3 case and k 4 .

   Our proof presents a new connection between the Long-

   uniformity number. Suppose we are given a graph Code and the Kneser graph, and relies on the high

   G (V , E) on V n r

   vertices with chromatic

   chromatic numbers of the Kneser graph[10] and the Schrijver graph[9]. We prove a certain maximization variant

   number (G) k

   . Dene an r-uniform hypergraph

   of the Kneser conjecture, namely that any coloring of the

   H (V , F) in the following way. The vertex set of H

   is identical to that of G . For every edge e E and for

   Kneser graph by fewer colors than its chromatic number, has many non-monochromatic edges.

   every

   (r 2) subset

   V0 V \ e

   we include the edge

   A hypergraph

   H (V , E)

   with vertices V and edges

   e V0

   in the edge set F of H . If F (H ) contains

   E 2V

   is 3-uniform if every edge in E has exactly 3

   multiple edges, we leave only one copy of each edge. The obtained hypergraph H is r -uniform on n vertices. Now we claim that k /(r 1) (H ) k . Indeed, a k –

   0

   coloring of G is also a k-coloring of H , implying the upper bound on (H ). To prove the lower bound, let f :V 1,……k be a k ' -coloring of H . Let G be a

   subgraph of G , whose vertex set is V and whose edge set is composed of all these edges of G that are monochromatic under f . It is easy to see that the degree of

   every vertex v V in G is at most (r 2) . Thus G is

   vertices. A legal -coloring of a hypergraph H is a function f :V [] such that no edge of H is

   monochromatic. The chromatic number of H is the minimal for which such a coloring exists.

   The best algorithms for these problems require a polynomial number of colors: for example the best approximate coloring algorithm for 2-colorable 3-uniform hypergraphs requires O(n1/ 5 ) colors [8], and the best

   coloring algorithm for 3-colorable graphs, requires

   0

   (r 1) -colorable. We infer that the edge set

   0

   E(G) of G

   ~

   O(n

   3 /14 ) colors .

   can be partitioned into two subsets

   E(G) \ E(G0 ) and

3. UNIFORM HYPERGRAPH COLORING

   '

   E(G0 ) such that the rst subset forms a k -colorable graph, while the second one is (r 1) -colorable. Then G is k ' (r 1) -colorable, as we can label each vertex

   by a pair whose rst coordinate is its color in a k ' –

   Definition 3.

   3-uniform: if each edge contains exactly 3 vertices,

   |e|=3.

   Definition 3.2

   2 Colorable, or has property B:

   if there exists a red-blue coloring of the vertices,

   coloration of the rst subgraph, and the second coordinate comes from an (r 1) -coloration of the second subgraph.

   Therefore G and H as dened above have the same number of vertices, and their chromatic numbers have the same order. Applying now the result[4], we get the following theorem.

   with no monochromatic hyper-edge Theorem 3.3

   Given a 3- uniform hypergraph, deciding whether or c is NP-hard,

   Proof

   2

   Theorem 2.1. Let r 3 be xed. If

   NP ZPP , it is

   The property of being 2-colorable is well studied in combinatorics and is also referred to as property B.

   impossible to approximate the chromatic number of r- uniform hypergraphs on n vertices within a factor of n1 for any xed 0 in time polynomial in n.

   We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP -hard for any constant c. The best known algorithm [8] colors such a graph using O(n1/ 5 ) colors. t

   Nevertheless, prior to this work no hardness of approximation result was known for 3-uniform hypergraphs, and in fact it wasnt even known if it is NP – hard to color a 3-uniform 2-colorable hypergraph with 3 colors. For 4-uniform hypergraphs and upwards ] were able to show such a separation, i.e., they showed that it is NP- hard to color a 2-colorable 4-uniform hypergraph with any constant number of colors . In their work, an inherent di erence between the case k 4 and the case k 2,3

   was raised; this was considered evidence that the case

   k 3 might be harder to understand. This di erence has

   to do with the corresponding maximization problem called Set-Splitting, which is the problem of 2-coloring a k- uniform hypergraph while maximizing the number of non- monochromatic hyperedges.

   Corollary

   For any constants k 3 and c2 c1 1, coloring a k – uniform c1 -colorable hypergraph with c2 colors is NP – hard; the case k 2 , however, remains wide open.

   Example

4. KNESAR GRAPH

In this section we dene the Kneser graph and describe some of its important properties. For n 2s 1 , the

The above Kneser Graph of

KG5,2

in Petersen graph

Kneser graph

n def

KGn,s

has the set

with 5 vertices and 2 subsets.

S n S

s

s

two vertices

S1 , S2

are adjacent i

S1 S2 . In

other words, each vertex corresponds to an s-set and two vertices are adjacent if their corresponding sets are disjoint. In this paper we are mainly interested in the case where s is smaller than n/2 by a constant. These graphs have the important property that the chromatic number is high although large independent sets exist. For a discussion of Kneser graphs and other combinatorial problems.

There exists a simple way to color this graph with

n 2s 2 coloring. It conjectured that there is no way to

The subsets are 1,2,3,4.5

and it satisfy of the

color the graph with less colors, i.e., Maximization variant: different for 3-unif and k>3.

(KGn,s ) n 2s 2 . Many other proofs and

i.e 1, 2,1,3,1, 4,1,5,2,3,2, 4,2,5,

extensions are known and the latest and simplest one. Our goal in this section is to prove the following property of the Kneser graph: in any coloring of the vertices of the Kneser graph with less colors than its chromatic number, there must exist many monochromatic edges. The way we prove this is by considering certain induced subgraphs of the Kneser graph known as Schrijver graphs. The proof follows from the fact that these induced subgraphs have the same chromatic number as the whole Kneser graph.

Definition 4.1

3, 4,3,5,4,5

CONCLUSION

We concludethat, the above informations sloving that the kneser Graph is given the approximation and Hardness of the hyper graph and also prove the applications of the Knesar graph. Some of Knesar graph G is label covering.Therefore without layers,the hypergraph is always 2-colourable.This is really the Long-Code Observation of the Knesar graph .

The Kneser Graph

KGn,s

is the graph whose vertices

REFERENCES

1. Lov´asz. Knesers conjecture, chromatic number, and

   correspond to the k -element subsets of a set of s elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. The chromatic

   homotopy. J. Combin. Theory Ser. A, 25(3):319324, 1978.

2. J. Brown, D. Corneil, Graph properties and hypergraph colourings, Discrete Math. 98 (1991) 8193.

   number of the Kneser graph KG

   n 2s 2

   n,s

   is exactly

3. H. Chen, A. Frieze, Coloring bipartite hypergraphs, in: Proc.

   5th Intern. IPCO Conference, in: Lecture Notes in Comput. Sci, Vol. 1084, 1996, pp. 345358.

4. U. Feige, J. Kilian, Zero knowledge and the chromatic number, in: Proc. 11th Annual IEEE Conf. on Computational Complexity, 1996.

5. T. Hofmeister, H. Lefmann, Approximating maximum independent sets in uniform hypergraphs, in: Proc. of the 23rd International Symposium on Mathematical Foundations of Computer Science, in: Lecture Notes in Comput. Sci., Vol. 1450, Springer-Verlag, 1998, pp. 562570.

6. J. HÃ¥stad, Clique is hard to approximate within n1 , in: Proc. 37th IEEE FOCS, IEEE Press, 1996, pp. 627 636..

7. T. Hofmeister, H. Lefmann, Approximating maximum independent sets in uniform hypergraphs, in: Proc. of the 23rd International Symposium on Mathematical Foundations

   of Computer Science, in: Lecture Notes in Comput. Sci., Vol. 1450, Springer-Verlag, 1998, pp. 562570.

8. M. Krivelevich, R. Nathaniel, and B. Sudakov. Approximating coloring and maximum inde- pendent sets in 3-uniform hypergraphs. J. Algorithms, 41(1):99113, 2001.

9. A. Schrijver. Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wisk. (3), 26(3):454 461, 1978.

10. M. Kneser. Aufgabe 360. Jahresbericht der Deutschen Mathematiker-Vereinigung, 58(2), Abteilung, S. 27, 1955.