Colourings, independence and domination in graphs and hypergraphs

Abstract

The definition of a hypergraph generalizes that of a graph by allowing edges to be subsets of the vortex set of any size. A hypergraph is said to be r uniform if all its edges are of size r. Thus, a simple graph is a 2-uniform hypergraph. ln this study, we deal with the fundamental graph-theoretic concepts of colouring, independence and domination, which are generalized for r-uniform hypergraphs. Multiple generalizations arise; for both coloring and independence, we consider two standard generalizations. We explain how these concepts are related to each other and we outline several upper bounds and lower bounds for associated parameters, such as the chromatic numbers, the independence numbers, the domination number, and the transversal number. We show how some of these bounds are attained by using explicit hypergraph constructions. ln doing so, we come across a class of Steiner systems. Another bound is shown to be asymptotically sharp by using a random hypergraph construction. Our investigation led us to a non-trivial definition of a hypergraph clique and to the problem of finding the minimum number of edges that force an r uniform hypergraph to be such a clique, and we present our solution to this. The use of powerful tools in combinatorics, such as the probabilistic method and the Kruskal-Katona Theorem, is key in obtaining these results. Turan's Theorem, which provides a lower bound for the independence number, states that the maximum number of edges in a complete r+ 1-partite tree graph is given by the number of edges in a Turan graph. We explore a generalisation of this result called the Erdos-Stone Theorem and give two separate proofs to this theorem.