Get Induced Matching essential facts below. View Videos or join the Induced Matching discussion. Add Induced Matching to your PopFlock.com topic list for future reference or share this resource on social media.
The minimum number of induced matchings into which the edges of a graph can be partitioned is called its strong chromatic index, by analogy with the chromatic index of the graph, the minimum number of matchings into which its edges can be partitioned. It equals the chromatic number of the square of the line graph. Brooks' theorem, applied to the square of the line graph,
shows that the strong chromatic index is at most quadratic in the maximum degree of the given graph, but better constant factors in the quadratic bound can be obtained by other methods.
The Ruzsa-Szemerédi problem concerns the edge density of balanced bipartite graphs with linear strong chromatic index. Equivalently, it concerns the density of a different class of graphs, the locally linear graphs in which the neighborhood of every vertex is an induced matching. Neither of these types of graph can have a quadratic number of edges, but constructions are known for graphs of this type with nearly-quadratic numbers of edges.
The problem is also W-hard, meaning that even finding a small induced matching of a given size is unlikely to have an algorithm significantly faster than the brute force search approach of trying all -tuples of edges. However, the problem of finding vertices whose removal leaves an induced matching is fixed-parameter tractable. The problem can also be solved exactly on -vertex graphs in time with exponential space, or in time with polynomial space.
^Ruzsa, I. Z.; Szemerédi, E. (1978), "Triple systems with no six points carrying three triangles", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, 18, Amsterdam and New York: North-Holland, pp. 939-945, MR0519318