Induced matching

[1] 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.

[2] 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.

[3] The Ruzsa–Szemerédi problem concerns the edge density of balanced bipartite graphs with linear strong chromatic index.

is NP-complete (and thus, finding an induced matching of maximum size is NP-hard).

Unless an unexpected collapse in the polynomial hierarchy occurs, the largest induced matching cannot be approximated to within any

[8] The problem is also W[1]-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

vertices whose removal leaves an induced matching is fixed-parameter tractable.

Each set of edges of the same color is an induced matching. Each color is a matching because none of these edges share a vertex, and is an induced subgraph because there are no edges of a different color directly connecting 2 vertices belonging to it. The minimum number of colors (induced matchings) needed to cover the graph is the graph's strong chromatic index .
3 colors are needed to cover cycles divisible by 3, and 4 are needed otherwise.