Partitioning an interval graph into subgraphs with small claws

MaRDI QIDQ6378411zbMATH OpenFDO

Authors Rain Jiang, Kai Jiang, Minghui Jiang

Publication date 23 September 2021

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 $checkkappa(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)=lfloorlo{g}_{v+1}(nv+1)floor$, and that $lfloorlo{g}_{v+1}wfloor+1lecheckkappa(w,v)lelfloorlo{g}_{v+1}wfloor+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 $1levle2$, and $2$ when $vge3$.

This page was built for publication: Partitioning an interval graph into subgraphs with small claws

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6378411)