<p>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.</p>
<p>As per my observations, this type of independent set size restriction has no relation to degree of vertex <em>k</em>, it can be any <em>k</em> and still graph can be 4-claw free.</p>
<p>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?</p>

CC BY-SA 4.0
2024-02-25T23:54:53.210Z
See the notions of inductively k-independent graphs (https://dl.acm.org/doi/abs/10.1145/2151171.2151177) and k-perfectly orientable graphs (https://link.springer.com/article/10.1007/s00453-012-9671-1).
Chandra Chekuri
CC BY-SA 4.0
2024-03-07T12:19:06.090Z
I don't understand this question. A large complete graph is 4-claw free and has only large vertex degrees.
Zsbán Ambrus
<graph-theory><independent-set><graph-classes><bounded-degree>
Is every 4-claw-free graph a bounded degree graph?
user72110
# Is every 4-claw-free graph a bounded degree graph?

(Asked by: username_0 on 2024-02-25)

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?

**Tags:** graph-theory, independent-set, graph-classes, bounded-degree
> **Comments:**
> **username_1**: See the notions of inductively k-independent graphs (https://dl.acm.org/doi/abs/10.1145/2151171.2151177) and k-perfectly orientable graphs (https://link.springer.com/article/10.1007/s00453-012-9671-1).  
> **username_2**: I don't understand this question. A large complete graph is 4-claw free and has only large vertex degrees.  

---

## 0 answers

