I am looking of some graph properties of 4-claw free graph, where neighborhood of every vertex has independent set of size at most 3.

As per my observations, this type of independent set size restriction has no relation to degree of vertex k, it can be any k and still graph can be 4-claw free.

however, Is there any co-relation between them? Can we seek inspiration from results for maximum independent set problem on bounded degree graphs to d-claw free graphs?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.