Partitioning an interval graph into subgraphs with small claws
share
The claw number of a graph G is the largest number v such that K_1,v is an induced subgraph of G. Interval graphs with claw number at most v are cluster graphs when v = 1, and are proper interval graphs when v = 2. Let κ(n,v) be the smallest number k such that every interval graph with n vertices admits a vertex partition into k induced subgraphs with claw number at most v. Let κ̌(w,v) be the smallest number k such that every interval graph with claw number w admits a vertex partition into k induced subgraphs with claw number at most v. We show that κ(n,v) = ⌊log_v+1 (n v + 1)⌋, and that ⌊log_v+1 w⌋ + 1 ≤κ̌(w,v) ≤⌊log_v+1 w⌋ + 3. Besides the combinatorial bounds, we also present a simple approximation algorithm for partitioning an interval graph into the minimum number of induced subgraphs with claw number at most v, with approximation ratio 3 when 1 ≤ v ≤ 2, and 2 when v ≥ 3.
READ FULL TEXT