ABSTRACT

The concept of H-decompositions of graphs was first introduced by Erdös, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. 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 be the smallest number, such that, any graph of order n admits an H-decomposition with at most parts. The exact computation of for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decompositions of graphs.

1. Introduction

1.1. Terminology and Notations

For notation and terminology not discussed here the reader is referred to [1]. A graph is a (finite) set, called the vertices of G together with a set of (unordered) pairs of vertices of G, called the edges. We do not allow loops and multiple edges. The number of vertices of a graph is its order and is denoted by. The number of edges in a graph is its size and is denoted by. A vertex is incident with an edge e if and the two vertices incident with an edge are called its endpoints. Two vertices of G are said to be adjacent or neighbors if is an edge of G. The degree of a vertex v is the number of edges incident with v and will be denoted by or simply by if it is clear which graph is being considered. The complete graph (clique) of order n will be denoted by, the complete bipartite graph with parts of size m and n will be denoted by and the cycle of length will be denoted by.

The Turán graph of order n, denoted by, is the unique complete -partite graph on n vertices where every partite class has either or vertices. The well-known Turán’s Theorem [2] states that is the unique graph on n vertices that has the maximum number of edges and contains no complete subgraph of order r. We let denote the number of edges in.

Finally, a proper colouring or simply a colouring of the vertices of G is an assignment of colours to the vertices in such a way that adjacent vertices have distinct colours; is then the minimum number of colours in a (vertex) colouring of G. For example, , and.

1.2. Motivation and Definitions

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 an H-subgraph, i.e., a graph isomorphic to H. We allow partitions only, that is, every edge of G appears in precisely one part. Let be the smallest possible number of parts in an H-decomposition of G. It is easy to see that , where is the maximum number of pairwise edge-disjoint H-subgraphs that can be packed into G. Building upon a body of previous research, Dor and Tarsi [3] showed that if H has a component with at least 3 edges, then the problem of checking whether an input graph G is perfectly decomposable into H-subgraphs is NP-complete. Hence, it is NP-hard to compute the function for such H. Therefore, the aim is to study the function

which is the smallest number such that any graph G of order n admits an H-decomposition with at most parts.

This function was first studied, in 1966, by Erdös, Goodman and Pósa [4], who were motivated by the problem of representing graphs by set intersections. They proved that. A decade later, this result was extended by Bollobás [5], who proved that, for all.

General graphs H were only considered recently by Pikhurko and Sousa [6]. In Section 2 we will present known results about the exact value of the function for some special graphs H and its asymptotic value for arbitrary H. In Sections 3 and 4 two new H-decomposition problems will be introduced, namely the weighted version and the monochromatic version respectively.

2. H-Decompositions of Graphs

In 1966, Erdös, Goodman and Pósa [4], who were motivated by the problem of representing graphs by set intersections, proved that and a decade later Bollobás [5] proved thatfor all. Recently, Pikhurko and Sousa [6] studied the function for arbitrary graphs H. They proved the following result.

Theorem 2.1. [6] Let H be any fixed graph with chromatic number. Then,

Let denote the maximum number of edges in a graph of order n, that does not contain H as a subgraph. Recall that. The same authors also made the following conjecture.

Conjecture 2.2. For any graph H with chromatic number at least 3, there is such that for all.

The exact value of the function is far from being known, however, this conjecture has been verified for some special graphs. The following results have been proved by Sousa.

Theorem 2.3. [7] For all we have

Theorem 2.4. [8] For all we have

For, a clique-extension of order is a connected graph that consists of a plus another vertex, say x, adjacent to at most vertices of. For the be the clique-extension of order that has.

Theorem 2.5. [9] For all and we have

Theorem 2.6. [9] Let and let be any cliqueextension of order. For all we have

A graph H is said to be edge-critical if there exists an edge whose deletion decreases the chromatic number, that is,. Cliques and oddcycles are examples of edge-critical graphs. Özkahya and Person [10] were able to prove that Pikhurko and Sousa’s conjecture is true for all edge-critical graphs. Their result is the following.

Theorem 2.7. [10] Let H be any edge-critical graph with chromatic number. Then, there exists such that, for all. Moreover, the only graph attaining is the Turán graph.

The case when H is a bipartite graph has been less studied. Pikhurko and Sousa [6] determined for any fixed bipartite graph with an additive error. For a non-empty graph H, let denote the greatest common divisor of the degrees of H. For example, , while for any tree T with at least 2 vertices we have. They proved the following result.

Theorem 2.8. [6] Let H be a bipartite graph with edges and let. Then there is such that for all the following statements hold.

If, then if,

otherwise,

where denotes any graph obtained from after deleting at most edges in order to have

. Furthermore, if is extremal then is either or.

If, then

Moreover, there is a procedure with running time polynomial in which determines and describes a family of -sequences such that a graph G of order satisfies if and only if the degree sequence of G belongs to. (It will be the case that and each sequence in has equal entries, so can be described using bits.)

3. Weighted H-Decompositions of Graphs

In 2011, Sousa [11] introduced a weighted version of the H-decomposition problem for graphs. More precisely, let G and H be two graphs and b a positive number. A weighted -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, i.e., a graph isomorphic to H. 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 be the smallest possible weight in an -decomposition of G.

As before, the goal is to study the function

which is the smallest number such that any graph G with n vertices admits an -decomposition with weight at most.

Note that when we take the original H-decomposition problem is recovered, hence, it suffices to consider the case when. Furthermore, when

we easily have. Thereforeone only has to consider the case when and. Sousa [11] obtained the asymptotic value of the function for any fixed bipartite graph H when and.

Recall that for a non-empty graph H, denotes the greatest common divisor of the degrees of H. Sousa proved the following result.

Theorem 3.1. [11] Let H be a bipartite graph with edges, let and with a constant. Then there is such that for all the following statements hold.

If, then

If, let where is an integer.

If and, then

If and, then

If and, then

If and, then

and

If and, then

The case when H is not a bipartite graph is still an open problem.

4. Monochromatic H-Decompositions of Graphs

In this section the H-decomposition problem is extended to coloured versions of the graph G and monochromatic copies of H. We define the problem more precisely.

A k-edge-colouring of a graph G is a function. We think of c as a colouring of the edges of G, where each edge is given one of k possible colours. Given a fixed graph H, a graph G of order n and a k-edge-colouring of the edges of G, 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 a monochromatic copy of H. Let be the smallest number such that, for any k -edge-colouring of G, there exists a monochromatic H-decomposition of G with at most elements. The objective is to study the function which is the smallest number such that, any k-edgecoloured graph of order n admits a monochromatic H-decomposition with at most elements.

This function was introduced recently by Liu and Sousa [12] and they studied the function for all and. Their results involve the Ramsey numbers and the Turán numbers. Recall that for and, the Ramsey number for, denoted by, is the smallest value of s, for which every k-edge-colouring of contains a monochromatic. The Ramsey numbers are notoriously difficult to calculate, even though, it is known that their values are finite for all and. In fact, for the Ramsey numbers, only three of them are currently known. In 1955, Greenwood and Gleason [13] were the first to determine, and. Liu and Sousa [12] proved the following results about monochromatic -decompositions.

Theorem 4.1. [12] Let. There is an such that, for all, we have

That is, and. Moreover, the only k-edge-coloured graph G attaining

is the Turán graph.

Theorem 4.2. [12] For all we have

The same authors also made the following conjecture.

Conjecture 4.3. Let k ≥ 4. Then for.

Larger cliques were also studied by Liu and Sousa and they obtained the exact value of the function for all and. Recall that the Ramsey number is also well-known.

Theorem 4.4. [12] Let,. There is an such that, for all, we have

In particular,. Moreover, the only graph attaining is the Turán graph

.

5. Acknowledgements

The author acknowledges the support from FCT—Fundação para a Ciência e a Tecnologia (Portugal), through the Projects PTDC/MAT/113207/2009 and PEst-OE/ MAT/UI0297/2011 (CMA).

REFERENCES