Partitioning an interval graph into subgraphs with small claws

Abstract

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 $\kappa (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 $\check{\kappa }(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 $\kappa (n,v)=\lfloor {\log }_{v+1}(nv+1)\rfloor$, and that $\lfloor {\log }_{v+1}w\rfloor +1\le \check{\kappa }(w,v)\le \lfloor {\log }_{v+1}w\rfloor +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\le v\le 2$, and $2$ when $v\ge 3$.

Cited by in corpus (1)

• Vertebrate interval graphs