Teresa Maria Jerónimo Sousa

Let k be a positive integer and G be a k-connected graph. In 2009, Chartrand, Johns, McKeon, and Zhang introduced the rainbow k-connection number rc_k(G) of G. An edge-coloured path is rainbow if its edges have distinct colours. Then, rc_k(G) is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by k internally vertex-disjoint rainbow paths. The function rc_k(G) has since been studied by numerous researchers. An analogue of the function rc_k(G) involving vertex colourings, the rainbow vertex k-connection number rvc_k(G), was subsequently introduced. In this paper, we introduce a version which involves total colourings. A total-coloured path is total-rainbow if its edges and internal vertices have distinct colours. The total rainbow k-connection number of G, denoted by trc_k(G), is the minimum number of colours required to colour the edges and vertices of $G$, so that any two vertices of $G$ are connected by $k$ internally vertex-disjoint total-rainbow paths. We study the function trc_k(G) when G is a cycle, a wheel, and a complete multipartite graph. We also compare the functions rc_k(G), rvc_k(G), and trc_k(G), by considering how close and how far apart trc_k(G) can be from rc_k(G) and rvc_k(G).

Given two graphs G and H, an H-decomposition of G is a partition of the
edge set of G such that each part is either a single edge or forms a graph
isomorphic to H. Let f(n;H) be the smallest number  such that any graph
G of order n admits an H-decomposition with at most f(n;H)  parts. Pikhurko and
Sousa conjectured that f(n;H) = ex(n;H) for (H)  3 and all sufficiently
large n, where ex(n;H) denotes the maximum number of edges in a graph on n vertices not containing H as a subgraph. Their conjecture has been veried by
Ozkahya and Person for all edge-critical graphs H. In this article, the conjecture
is veried for the k-fan graph. The k-fan graph, denoted by F_k, is the graph on
2k + 1 vertices consisting of k triangles which intersect in exactly one common
vertex called the centre of the k-fan.

Let k be a positive integer and G be a k-connected graph. An edge-coloured path is rainbow if its edges have distinct colours. The rainbow k-connection number of G, denoted by rc_k(G), is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by k internally vertex-disjoint rainbow paths. The function rc_k(G) was first introduced by Chartrand, Johns, McKeon, and Zhang in 2009, and has since attracted considerable interest. In this paper, we consider a version of the function rc_k(G) which involves vertex-colourings. A vertex-coloured path is vertex-rainbow if its internal vertices have distinct colours. The rainbow vertex k-connection number of G, denoted by rvc_k(G), is the minimum number of colours required to colour the vertices of G so that any two vertices of G are connected by k internally vertex-disjoint vertex-rainbow paths. We shall study the function rvc_k(G) when G is a cycle, a wheel, and a complete multipartite graph. We also construct graphs G where rc_k(G) is much larger than rvc_k(G) and vice versa so that we cannot in general bound one of rc_k(G) and rvc_k(G) in terms of the other.

Given graphs G and H, and a coloring of the edges of G with k colors, a monochromatic H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a monochromatic graph isomorphic to H. Let f_{k}(n,H) be the smallest number t such that any graph G of order n and any coloring of its edges with k colors, admits a monochromatic H-decomposition with at most t parts. Here we study the function f_{k}(n,K_r) for k≥ 2 and r≥ 3.

Given graphs G and H, and a coloring of the edges of G with k colors, a monochromatic H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a monochromatic graph isomorphic to H. Let f_{k}(n,H) be the smallest number t such that any k-edge-colored graph G of order n, admits a monochromatic H-decomposition with at most t parts. Here we study the function f_{k}(n,K_r) for k ≥2 and r≥ 3.