Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to find them. My intuition is to approach this with $k$ colors, but not really sure how to start it. Could someone give me some hints and ideas on how to approach this?
Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?
graph theory;graphs;randomized algorithms;bipartite matching;colorings