An Integrative Theory of Circular Colourings of Hypergraphs

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.

1. 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 non-empty subsets of . If is one-to- one, and no one-subset 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 2-uniform 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 2-uniform hypergraph, is a subhypergraph of

   . In the case of 2-uniform 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,

   1. 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, () =

   2. 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 non-singleton 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 2-subset 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, / /.

   3. 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, C-Perfect 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), 371

410.

[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).