Suppose we have a graph $G=(V,E)$ connected and $K_{1,3}$-free. Sumner proved that every claw-free connected graph with an even number of vertices has a perfect matching (so, it is maximum matching).

Describe an algorithm to construct one matching of cardinality $|V|/2$ in $G$ in time compelxity $O(|V|+|E|)$.

I thought it in this way: the BFS tree of $G$ is acyclic so a topological sort (postorder traversal) on it may solve the problem (via https://en.wikipedia.org/wiki/Claw-free_graph). But, looking some examples, I realized that there may exist edges that don't belong to $E$.

  • $\begingroup$ I'm curious: is Sumner's proof not constructive? Or is it, but you are trying to solve the problem for yourself? $\endgroup$ – G. Bach Nov 26 '15 at 12:32
  • $\begingroup$ @G.Bach of course it is, but constructing that matching in this way and select two by two nodes in postorder traversal, it seems that some edges that are not present in $G$ appear. Or do I something wrong..I don`t know:D $\endgroup$ – penguina Nov 26 '15 at 14:47
  • $\begingroup$ Is the material available online somewhere? $\endgroup$ – G. Bach Nov 26 '15 at 16:28
  • $\begingroup$ Look at en.wikipedia.org/wiki/Claw-free_graph section Matchings $\endgroup$ – penguina Nov 26 '15 at 16:33
  • 1
    $\begingroup$ Try using the fact that a DFS tree of a claw-free graph is binary. If it works out, perhaps you could answer your own question. $\endgroup$ – Yuval Filmus Nov 26 '15 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.