Publications

Export 5 results:
Sort by: Author [ Title  (Asc)] Type Year
A B C D E F G H I J K L [M] N O P Q R S T U V W X Y Z   [Show ALL]
M
Pikhurko, Oleg, and Teresa Sousa. "Minimum H-Decompositions of Graphs." Journal of Combinatorial Theory, B. 97 (2007): 1041-1055. Abstracth_decomposition.pdfWebsite

Given 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 φH(n) be the smallest number φ such that every graph G of order n admits an H-decomposition with at most φ parts. In the paper it is proved that φH(n)=tr−1(n)+o(n2) for every graph H of chromatic number r≥3, where tr(n) is the maximum size of an r-partite graph of order n. Moreover, when H is bipartite, the authors determine φH(n) with a constant additive error.

Sousa, Teresa. "Minimum Weight H-Decompositions of Graphs: The Bipartite Case." Electronic Journal of Combinatorics. 18(1) (2011): P126, 10 pp. AbstractWeighted_bipartite_decompositions.pdfWebsite

Given graphs G and H and a positive number b, a weighted (H,b)-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms an H-subgraph. We assign a weight of b to each H-subgraph in the decomposition and a weight of 1 to single edges. The total weight of the decomposition is the sum of the weights of all elements in the decomposition. Let f(n,H,b) be the the smallest number such that any graph G of order n admits an (H,b)-decomposition with weight at most f(n,H,b). The value of the function f(n,H,b) when b=1 was determined, for large n, by Pikhurko and Sousa [Pikhurko, O. and Sousa, T., Minimum H-Decompositions of Graphs, Journal of Combinatorial Theory, B, 97 (2007), 1041--1055.Here we determine the asymptotic value of f(n,H,b)for any fixed bipartite graph H and any value of b as n tends to infinity.

H., Liu, Pikhurko O., and Sousa Teresa. "Monochromatic Clique Decompositions of Graphs." Journal of Graph Theory. 80 (2015): 287-298. Abstractgeneral-mono-clique.pdf

Let $G$ be a graph whose edges are coloured with $k$ colours, and $\mathcal H=(H_1,\dots , H_k)$ be a $k$-tuple of graphs. A \emph{monochromatic $\mathcal 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 copy of $H_i$ in colour $i$, for some $1\le i\le k$. Let $\phi_{k}(n,\mathcal H)$ be the smallest number $\phi$, such that, for every
order-$n$ graph and every $k$-edge-colouring, there is a monochromatic $\mathcal H$-decomposition with at most $\phi$ elements. Extending the previous results of Liu and Sousa [``Monochromatic $K_r$-decompositions of graphs", \emph{Journal of Graph Theory}76:89-100,2014], we solve this problem
when each graph in $\mathcal H$ is a clique and $n\ge n_0(\mathcal H)$ is sufficiently large.

Liu, H., and Teresa Sousa. "Monochromatic K_r-Decompositions of Graphs." Journal of Graph Theory. 76 (2014): 89-100. Abstractmono-clique-preprint.pdf

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.

Liu, H., and Teresa Sousa. "Monochromatic K_r-Decompositions of Graphs." Electronic Notes in Discrete Mathematics. 43 (2013): 121-127. Abstractmono-clique-ep100.pdf

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.