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?

  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Dec 2 '14 at 6:18
  • $\begingroup$ hey, they are vertex-disjoint. 4k colors,hmmm, how does 4k colors give each claw a unique color? $\endgroup$ – 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).

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.