Maximum induced matchings of random cubic graphs

摘要

We present a heuristic for finding a large induced matching of cubic graphs. We analyse the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations and obtain a lower bound on the expected size of the induced matching, M, returned by the algorithm. A corresponding upper bound is derived by means of a direct expectation argument. We prove that M asymptotically almost surely satisfies 0.270413n⩽|M|⩽0.282069n.