We consider a generalisation of proper vertex colouring of graphs, referred to as improper colouring, in which each vertex can only be adjacent to a bounded number t of vertices with the same colour, and we study this type of graph colouring problem in several different settings. The thesis is divided into six chapters. In Chapter 1, we outline previous work in the area of improper colouring. In Chapters 2 and 3, we consider improper colouring of unit disk graphs -- a topic motivated by applications in telecommunications -- and take two approaches, first an algorithmic one and then an average-case analysis. In Chapter 4, we study the asymptotic behaviour of the improper chromatic number for the classical Erdos-Renyi model of random graphs. In Chapter 5, we discuss acyclic improper colourings, a specialisation of improper colouring, for graphs of bounded maximum degree. Finally, in Chapter 6, we consider another type of colouring, frugal colouring, in which no colour appears more than a bounded number of times in any neighbourhood. Throughout the thesis, we will observe a gradient of behaviours: for random unit disk graphs and "large" unit disk graphs, we can greatly reduce the required number of colours relative to proper colouring; in Erdos-Renyi random graphs, we do gain some improvement but only when t is relatively large; for acyclic improper chromatic numbers of bounded degree graphs, we discern an asymptotic difference in only a very narrow range of choices for t.

An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. The smallest number of colours needed to colour a graph G with a star edge colouring is called the star chromatic index of G and is denoted <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(G)" />. This paper proves an upper bound of the star chromatic index of bipartite graphs in terms of the maximum degree; the maximum degree of G is the largest number of edges incident to a single vertex in G. For bipartite graphs Bk with maximum degree <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?k%5Cgeq1" />, the star chromatic index is proven to satisfy<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%20%5Cchi'_%7Bst%7D(B_k)%20%5Cleq%20k%5E2%20-%20k%20+%201" />. For bipartite graphs <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?B_%7Bk,n%7D" />, where all vertices in one part have degree n, and all vertices in the other part have degree k, it is proven that the star chromatic index satisfies <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(Bk,n)%20%5Cleq%20k%5E2%20-2k%20+%20n%20+%201,%20k%20%5Cgeq%20n%20%3E%201" />. We also prove an upper bound for a special case of multipartite graphs, namely <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?K_%7Bn,1,1,%5Cdots,1%7D" /> with m parts of size one. The star chromatic index of such a graph satisfies<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(K_%7Bn,1,1,%5Cdots,1%7D)%20%5Cleq%2015%5Clceil%5Cfrac%7Bn%7D%7B8%7D%5Crceil%5Ccdot%5Clceil%5Cfrac%7Bm%7D%7B8%7D%5Crceil%20+%20%5Cfrac%7B1%7D%7B2%7Dm(m-1),%5C,m%20%5Cgeq%205" />. For complete multipartite graphs where m &lt; 5, we prove lower upper bounds than the one above.

For a set of graphs H, we call a graph G H-free if G-S is non-isomorphic to H for each S⊆V(G) and each H∈H. Let f_H^* ∶N_(>0)↦N_(>0 )be the optimal χ-binding function of the class of H-free graphs, that is, f_H^* (ω)=max⁡{χ(G): ω(G)=ω,G is H-free} where χ(G),ω(G) denote the chromatic number and clique number of G, respectively. In this thesis, we mostly determine optimal χ-binding functions for subclasses of P_5-free graphs, where P_5 denotes the path on 5 vertices. For multiple subclasses we are able to determine them exactly and for others we prove the right order of magnitude. To achieve those results we prove structural results for the graph classes and determine colourings. We sometimes obtain those results by researching the prime graphs and combining the two decomposition methods by homogeneous sets and clique-separators. Additionally, we use the Strong Perfect Graph Theorem and analyse the neighbourhood of holes. For some of these subclasses we characterise all graphs G with χ(G)>χ(G-\{u\}), for each u∈V(G) and use those to determine the function.