 Open Access
 Total Downloads : 177
 Authors : Dr. (Mrs). B. Tamilselvi, Ms. A. Kiruthika, Mrs. K. Banupriya, Ms. S. K. Sathya
 Paper ID : IJERTV2IS120098
 Volume & Issue : Volume 02, Issue 12 (December 2013)
 Published (First Online): 06122013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
An Integrative Theory of Circular Colourings of Hypergraphs
Dr. (Mrs). B. Tamilselvi, Ms. A. Kiruthika, Mrs. K. Banupriya, Ms. S. K. Sathya
Dr.(Mrs).B. Tamilselvi is currently working as an Associate Professor in PSGR Krishnammal College for Women, Coimbatore, .
Ms.A.Kiruthika, Mrs.K. Banupriya and Ms.S.K. Sathya are currently pursuing their M.Phil Degree in PSGR Krishnammal College for Women, Coimbatore, India.
Abstract
Colouring is one of the important branches of graph theory and has attracted the attention of almost all graph theorists, mainly because of the four colour theorem. This paper is concerned with circular colourings of hypergraphs and it is based on the results of Bondy and Hell. This paper also includes, few examples for this circular colourings of hypergraphs.
Keywords: Chromatic number, Circular Chromatic number, Clique number, Hypergraph, (, ) – colourings, uniform hypergraph, Pigeonhole Principle, universal vertex.

Indroduction
In what follows hypergraphs are simple and finite unless otherwise specified. A hypergraph is an ordered triple = (, , ), where is a set of objects called vertices, is a set of objects called edges, and the incidence function maps E to the set of nonempty subsets of . If is oneto one, and no onesubset of is in its range, then the hypergraph is called simple. The hypergraph is called finite if its vertex set is finite. A finite, simple hypergraph can be defined as an ordered pair = (, ), where is a finite set of objects called vertices and is a set of subsets of , each of which contains at least two vertices.
A subhypergraph of a hypergraph is a hypergraph such that () () and
() (). I () and is the hypergraph with vertex set () = and edge set ( ) = () , then
is a restatement of the definition of a colouring of a graph. A colourable hypergraph is one that has a colouring. Every hypergraph = (, ) is – colourable: assign a different colour to every vertex of . The smallest integer for which
is colourable is called the chromatic number of
, and is denoted by ().
An independent set in a hypergraph
= (, ) is a subset such that no edge
is a subset of . In a colouring of , the set of vertices that are assigned colour is an independent set.
Let 1 and 2 be hypergraphs. A homomorphism of 1 to 2 is a function
(1 ) (2 ) such that () (2 ) for every edge (1 ). If there exists a homomorphism of 1 to 2 , then it is denoted as
1 2 , or 1 2 to emphasize the name, , of the mapping. If 1 2 then, for every vertex (2 ), the set 1() is an independent set. Let and be positive integers
such that 2.
A (, )colouring of a hypergraph
= (, ) is a function such that for each edge there exist a pair of vertices
{, } such that () () . The infimum of the set of ratios / such that has a (, )colouring is called the circular chromatic number of and is denoted by (). A (, )colouring of a graph is a function
() such that if () then
() () . The circular chromatic number of , denoted () is the infimum of the set of ratios / such that has a (, )colouring. For positive integers and with
2, we define to be the hypergraph with
is the subgraph of induced by . A hypergraph is called uniform if every edge has cardinality . A
vertex set
and edge set consisting of the subsets
simple graph = (, ) is therefore a 2uniform hypergraph and will sometimes be regarded as such.
of for which there exist vertices ,
such that   . This generalizes the corresponding concept for graphs: for positive
integers and with 2, the graph is
Let = (, ) be a hypergraph. A –
colouring of H is a function such
defined to have vertex set
=
and edge
set
that no edge of is monochromatic. Thus, if has a colouring, then every edge contains vertices and such that, () (). For 2 uniform hypergraphs (i.e. undirected graphs), this
= { }. Here , considered as a 2uniform hypergraph, is a subhypergraph of
. In the case of 2uniform hypergraphs, a graph G has a (, )colouring if and only if
and () is known to be the minimum of the set of ratios / such that .
Definition(Pigeonhole Principle): Suppose
, and are integers such that > + . If P pigeons are placed into pigeonholes, then the pigeonhole principle states there must be (at least) one pigeonhole which contains at least + 1 pigeons.
Similarly, recolour the vertices of colour 3 with colour 3 1, as above this is still a (, )colouring since there are no vertices of colour 2. As (, ) = 1, there exists a
unique such that 1 ( ), Then it will continue in this way with colours 4, 5, . , 1 ( ) to obtain a new (, ) colouring . Formally,

Circular Colourings Of Hypergraphs
c'(u) =
() 1, () = . 2
(),
Denote by the set {, 2, . , } and
This section computes the circular chromatic number of hypergraphs in various families. Some basic results concerning circular colourings are proved along the way.
Theorem 2.1 Let = (, ) be a hypergraph. If
has a (, )colourings and / /, where
and positive intergers, then has a
(, )colouring.
Proof Let be a (, )colouring of .
Define a mapping by
() =[/. ()] .
Consider an edge , and in particular the two
vertices and of such that () () . Assume that () ().
Since is a (, )colourings of , and
() () .
define to be the set .
Again recolour any vertex with the colour { }.
Since  =  = . By relabeling the colours of to be from the set
{0, 1, , ( 1) }. Set = .Thus, the modified mappings is now a mapping
. As 1 ( ). Here
1 = for some .
Define = . Next part of this theorem is to show that is a (, )colouring of
H. Consider the interval
= {, + 1, . , + 1} of .
Each interval contains the same number of elements of , by construction, with the exception of 1 which begins and ends with as element of , namely and . Thus 1 contains one more elements of than do the other intetvals.
Therefore,
() + = [/. () + ()/] = ()
As contains exactly = +1
elements of
Since + and
= [/. ()]
Therefore () +
(i.e.) () ()
Thus is a (, )colouring of .
Corollary 2.2 If has a (, )colouring, then it has a (, )colouring with / = / and (, ) = 1.
Theorem 2.3 Let be a hypergraph on vertices. If has a , – colouring which is not onto , then has a (, )colouring with
and / /.
Proof Let be a (, )colouring of .Using Corollary 2.2 and assume that (, ) = 1. Since is not onto, some colour is not used. Assume that this colour is . Now remove the colours that are a multiple of (taken modulo ) by recolouring the vertices as follows. Recolour
vertices of colour 2 with colour 2 1. Since no vertex is coloured this is still a (, )colouring.
and   = , each interval ( 1) contains elements of . Since 1 contains the colour one, 1 contains +1 elements of .
Consider any two vertices and such that () () . As each interval
( 1), has had elements removed. Since
() () = . The interval 1 as the colour is not used in the colouring and thus a colour difference of less than is not possible.
Thus, () () . Hence, is a (, )colouring of with
/ = ( )/ ( ) < / .
Corollary 2.4 Let = (, ) be a hypergraph. If has a (, )colouring then we may assume is onto.
The following corollary implies that the circular chromatic number of a hypergraph is rational.
Corollary 2.5 If is a hypergraph on n vertices, then
= {/: ,
}.
Proof Using Theorem 2.3 and Corollary 2.4. If
has a , – colouring, then it has a
(, ) – colouring with ' n and / /.
Thus,
() = inf{/: (, )
}.
Since this set is finite, the result follows.
Lemma 2.6 The maximum size of an independent set in the hypergraph is .
Proof Clearly the set {0,1, . . , 1} is independent, therefore the maximum size of an independent set in the hypergraph is atleast .
Let be a ( + 1)subset of ( ). Claim that is not an independent set. Suppose the
A hypergraph = (, ) with at least one edge is bipartite if can be partitioned into two independent sets. Clearly, is bipartite if and only if () = 2 .
Proposition 2.10 Let = (, ) be a hypergraph with at least one edge. Then
() 2 with equality if and only if is bipartite.
Proof It follows directly from the definition of the circular chromatic number that () 2.
If is bipartite, then using Theorem 2.8
gives () () = 2. Therefore, () =

Conversely, if () = 2 then using Corollary
contrary. By symmetry, it can be assumed that
. If contains a vertex not in
2.9 gives () = [
]
= 2. Therefore H is
{1, 2, ,2 1}, then is not an independent set as   . Therefore, {1, 2, ,2 1}. Since  = + 1, by the Pigeonhole Principle, some of the two elements , are congruent modulo . But then   = , so is not an independent set. This completes the Proof.
Proposition 2.7 The hypergraph has circular chromatic number /.
Proof Suppose : is a homomorphism.
bipartite.
A clique of a hypergraph is a complete subhypergraph. The clique number of , denoted
(), is the maximum size of a clique in . In a
colouring of a clique each vertex must receive a different colour. Hence for any , () () . Using Proposition 2.7 gives ( ) = /.
1
1
Therefore ( ) = = ().
Let = (, ) be a hypergraph. Vertex
is universal if every nonsingleton subset of
Since the maximum size of an independent set in the hypergraph is and also the inverse image
of an independent, set in is an independent set
containing is an edge of .
Theorem 2.11 If the hypergraph = (, ) has
in , it follows that for any integer
,
a universal vertex , then () = ().
Proof Suppose () = / and let
: be a (, )colouring of . Then, for
+1
every edge
there exist vertices
,
1( )
such that () ()
. Since
Hence,
=
1 +1
= 1( )
is a universal vertex, {, } for every vertex
{}.
Assume () = . Thus, ()
{0,1, , 2} for every vertex V{}.
Define : {0,1,,[/] 1} by
= [()/]. Then, since was a
=0 =
Therefore, / /
Theorem 2.8 For any hypergraph ,
1 < () .
Proof Let be a hypergraph with chromatic
number ().
Suppose () = / 1. Therefore,
1
1
there is a homomorphism ()1, and thus
a (() 1,1)colouring, contradicting the definition of the chromatic number.
Thus, () 1< ().On the other hand, here
() thus, () (). Finally
(, )colouring of , for every edge there exist vertices , such that () (). Therefore, [/] =[ c ]. It follows that
() = ()
Lemma 2.12 Let be a hypergraph, then
() ()
Proof Suppose is a clique in of size ().
Since every vertex of is universal in , It follows that () = () = (). Thus,
() () = ().
Corollary 2.13 Let be a hypergraph. If () = (), then () = ()
1
() 1 < () ().
Corollary 2.9 Let be a hypergraph. Then
() = [ ()]
Proof Using Lemma 2.12 () ()
() .The result follows.
Corollary 2.14 Let = (, ) be a complete
partite hypergraph. Then () = () =
Using Lemma 2.6 gives the maximum size of an independent set in the hypergraph (k) is ,
.
Proof Suppose that 1 , 2, , is a partition of
such that
= { , , 1 } . Since any 2subset of not contained in any block of the partition is an edge, it is clear that
() = . The subhypergraph induced by a set of vertices, one from each block of the partition, is a clique of size .
it follows that for any integer ,
+1
1 ()
=
Hence
1 +1
= 1 ()
=0 =
Thus () = = (). It now follows that
() = .
Theorem 2.15 Let = (, ) be a complete – uniform hypergraph on n vertices. Then
() = /( 1) and () = [/( 1)]
Proof Suppose , where , is a
homomorphism. Since any subset of is an edge, the maximum size of an independent set in is 1 and the inverse image of an independent set
in is independent. Thus, for any integer
Therefore, / /.

CONCLUSION

Finally this paper concludes, if the hypergraph has a universal vertex , then the chromatic numbers and the circular chromatic numbers are equal. And also if is a hypergraph then the chromatic numbers, the
Hence,
+1
1() 1
=
1 +1
circular chromatic numbers and the Clique
numbers are all equal.
ACKNOWLEDGMENT
The authors thank the referees for a careful reading of the manuscript. The authors also
= 1() ( 1)
gratefully acknowledge the support of the P.S.G.R.Krishnammal College for Women for the
=0 =
Therefore, /( 1) /.
Claim that the function :
valuable support.
defined by
() =
is an
(,
1
1)colouring of
REFERENCES
. Let be a subset of . By symmetry, it can be assumed without loss of generality that
1 . If cntains a vertex which is not in the set {1, 2, . . , 2( 1) 1} , then
( 1)  1.
If {1, 2, . , 2( 1) 1} then,
since  = , by the Pigeonhole principle, some two elements , are congruent modulo .
Thus,   = 1. Hence, any
set contains a pair of vertices and such that
() () = 1. This proves the claim. Therefore, () = /( 1) and Using Corollary 2.9 Finally () =[/( 1)] .
Proposition 2.16 For every rational number
/ 2 there exists a uniform hypergraph
= (, ) such that () = /.
Proof Let be an integer such that .
Consider the hypergraph (k). Since (k) is
[1]. J.A. Bondy and P. Hell, A Note on the Star Chromatic Number, J.Graph Theory, 14, (1988), 479 482. [2]. C. Eslahchi and Rafiey, Circular Chromatic Number of Hypergraphs Arc Combinatoria, 73, (2004), 239 246. [3]. C. Eslahchi and Rafiey, CPerfect K Uniform Hypergraphs , To appear in Arc Combinatoria. [4]. D.B. West, Introduction to Graph Theory, Prentice Hall, New Jersey, 1996. [5]. X. Zhu, Circular Chromatic Number, a survey, Discrete Math, 229 (2001), 371410.
[6]. Narasing Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice Hall of India Private Limited, New Delhi,2001.
the subhypergraph of induced by the edges of cardinality , c( (k)) (/) = /.
Suppose : (k) is a (, )colouring of
[7]. Doughlas B.West, Introduction to Graph Theory, Prentice Hall of India Private Limited, New Delhi, 2001.
(k).