Combinatorics Seminar

When: Sunday, October 28, 10am Where: Schreiber 309 Speaker: Raphael Yuster, University of Haifa Title: Edge-disjoint induced subgraphs with given minimum degree

Abstract:

Problems concerning edge-disjoint subgraphs that share some specified property are extensively studied in graph theory. Many fundamental problems, such as edge-coloring, vertex-coloring and graph packing, can be formulated in this way.

In this talk we consider the problem of determining the maximum size of a family of edge-disjoint *induced* subgraphs that have (each) some given minimum degree.

We give an asymptotically optimal answer to this problem, both for the maximum size of such a family (expressed in terms of the number of vertices, the number of edges, and the required minimum degree) while, at the same time, keeping the vertex-intersection of any two subgraphs as small as possible.