# Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?

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?

• Also, I haven't thought this through properly yet, so take it with a large grain of salt; perhaps using $4k$ colours is the key - so each claw is uniquely coloured. – Luke Mathieson Dec 2 '14 at 6:18
• hey, they are vertex-disjoint. 4k colors,hmmm, how does 4k colors give each claw a unique color? – hysoftwareeng Dec 2 '14 at 6:29

Finding vertex-disjoint copies of a subgraph $H$ in a graph $G$ is known as Graph Packing.
You could use Divide and Color to find the claws in $O^*(4^k)$, also deterministically (look for Chen et al. construction of universal set for derandomization).