# Partitioning an interval graph into subgraphs with small claws

Rain Jiang  Kai Jiang  Minghui Jiang
Home School, USA  dr.minghui.jiang at gmail.com

###### 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\leq\check{\kappa}(w,v)\leq\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\leq v\leq 2$, and $2$ when $v\geq 3$.

##  1 Introduction

The _intersection graph_ $G$ of a family $\mathcal{F}$ of sets is a graph such
that the vertices in $G$ correspond to the sets in $\mathcal{F}$, one vertex
for each set, and an edge connects two vertices in $G$ if and only if the
corresponding two sets in $\mathcal{F}$ intersect. A family $\mathcal{F}$ of
sets is called the _representation_ of a graph $G$ if $G$ is the intersection
graph of $\mathcal{F}$.

An _interval graph_ is the intersection graph of a family of open intervals.
Subclasses of interval graphs can be defined by imposing various restrictions
on the interval representation. A _proper interval graph_ is the intersection
graph of a family of open intervals in which no one properly contains another.
A _unit interval graph_ is the intersection graph of a family of open
intervals of the same length. It is well-known that an interval graph is a
proper interval graph if and only if it is a unit interval graph, and if and
only if it is $K_{1,3}$-free; see [4] for a self-contained elementary proof.

The _claw number_ $\psi(G)$ of a graph $G$ is the largest number $v\geq 0$
such that $G$ contains the star $K_{1,v}$ as an induced subgraph [2]. In
particular, a graph with claw number $0$ is an empty graph without any edges.
A graph with claw number at most $1$ is simply a disjoint union of cliques,
and is known as a _cluster graph_. Clearly, every cluster graph is an interval
graph, with claw number at most $1$. A proper / unit interval graph is an
interval graph with claw number at most $2$.

In this paper, we study vertex-partitions of an interval graph into induced
subgraphs with small claw numbers. A _$k$ -partition_ of a graph refers to a
partition of its vertices into $k$ subsets, and the resulting $k$ vertex-
disjoint induced subgraphs. For $k\geq 1$ and $v\geq 1$, let $\mu(k,v)$ be the
largest number $n$ such that any interval graph with $n$ vertices admits a
vertex partition into $k$ induced subgraphs with claw number at most $v$.
Correspondingly, for $n\geq 1$ and $v\geq 1$, let $\kappa(n,v)$ be the
smallest number $k$ such that any interval graph with $n$ vertices admits a
vertex partition into $k$ induced subgraphs with claw number at most $v$.

The _subchromatic number_ of a graph is the smallest number $k$ such that the
graph admits a $k$-partition into cluster graphs [3]. Broersma et al. [5,
Lemma 2.4] proved that the subchromatic number of any interval graph with $n$
vertices is at most $\lfloor\log_{2}(n+1)\rfloor$ and this bound is best
possible. Thus $\kappa(n,1)=\lfloor\log_{2}(n+1)\rfloor$. Gardi [9,
Proposition 2.2] showed that for all $n\geq 1$, there exists an interval graph
with $n$ vertices that admits no vertex partition into less than
$\lfloor\log_{3}(2n+1)\rfloor$ proper interval subgraphs. Thus
$\kappa(n,2)\geq\lfloor\log_{3}(2n+1)\rfloor$. The matching upper bound of
$\kappa(n,2)\leq\lfloor\log_{3}(2n+1)\rfloor$ was not known.

Extending the two previous results [5, 9], we determine exact values of
$\mu(k,v)$ and $\kappa(n,v)$ for all $v\geq 1$:

######  Theorem 1.

For $k\geq 1$ and $v\geq 1$, $\mu(k,v)=((v+1)^{k+1}-(v+1))/v$.

######  Corollary 1.

For $n\geq 1$ and $v\geq 1$, $\kappa(n,v)=\lfloor\log_{v+1}(nv+1)\rfloor$.

For $k\geq 1$ and $v\geq 1$, let $\check{\mu}(k,v)$ be the largest number $w$
such that any interval graph with claw number at most $w$ admits a vertex
partition into $k$ induced subgraphs with claw number at most $v$.
Correspondingly, for $w\geq v\geq 1$, let $\check{\kappa}(w,v)$ be the
smallest number $k$ such that any interval graph with claw number at most $w$
admits a vertex partition into $k$ induced subgraphs with claw number at most
$v$.

Clearly, $\check{\mu}(k,v)=v$ for $k=1$ and $v\geq 1$, and
$\check{\kappa}(w,v)=1$ for $w=v\geq 1$. Our next two results include bounds
on $\check{\mu}(k,v)$ for $k\geq 2$ and $v\geq 1$, and on
$\check{\kappa}(w,v)$ for $w>v\geq 1$:

######  Theorem 2.

For $k\geq 2$ and $v\geq 1$, $\check{\mu}(k,v)\leq(v+1)^{k}-1$. Also, for
$k\geq 2$, $\check{\mu}(k,v)\geq(v+1)^{k-1}/2$ when $v=1$,
$\check{\mu}(k,v)\geq 2(v+1)^{k-1}/3$ when $v=2$, and
$\check{\mu}(k,v)\geq(v-2)(v+1)^{k-1}$ when $v\geq 3$.

######  Corollary 2.

For $w>v\geq 1$,
$\lfloor\log_{v+1}w\rfloor+1\leq\check{\kappa}(w,v)\leq\lfloor\log_{v+1}w\rfloor+3$.
Moreover, for $w>v$,

  * •

$\check{\kappa}(w,v)\leq\lfloor\log_{v+1}2(w-1)\rfloor+2\leq\lfloor\log_{v+1}w\rfloor+3$
when $v=1$,

  * •

$\check{\kappa}(w,v)\leq\lfloor\log_{v+1}3(w-1)/2\rfloor+2\leq\lfloor\log_{v+1}w\rfloor+3$
when $v=2$,

  * •

$\check{\kappa}(w,v)\leq\lfloor\log_{v+1}(w-1)/(v-2)\rfloor+2\leq\lfloor\log_{v+1}w\rfloor+2$
when $v\geq 3$.

In the terminology of partially ordered sets [7], $\kappa(n,v)$ is the
smallest number $k$ such that any interval order with $n$ elements admits a
partition into $k$ weak orders (respectively, semiorders) when $v=1$
(respectively, $v=2$). Similarly, $\check{\kappa}(w,v)$ for $v=1$ and $v=2$
has alternative interpretations in terms of weak orders and semiorders in
interval orders.

Albertson et al. [3, Theorem 4] proved that $\check{\kappa}(w,1)\leq w$ for
any $w\geq 1$. Although this upper bound is asymptotically weaker than the
$v=1$ case of our upper bound in Corollary 2, it is tight for $w=2$ and $3$,
as we show in the next theorem, where the exact values of
$\check{\kappa}(w,v)$ are determined for some small values of $w$ and $v$:

######  Theorem 3.

$\check{\kappa}(2,1)=2$, $\check{\kappa}(3,1)=3$, $\check{\kappa}(3,2)=2$,
$\check{\kappa}(4,2)=\check{\kappa}(5,2)=\check{\kappa}(6,2)=3$,
$\check{\kappa}(5,3)=2$.

For $v\geq 1$, let Min-Partition$(v)$ be the problem of finding a vertex
partition of a given graph into the minimum number of induced subgraphs with
claw number at most $v$. For $k\geq 2$ and $v\geq 1$, let $k$-Partition$(v)$
be the problem of deciding whether a given graph admits a vertex partition
into $k$ induced subgraphs with claw number at most $v$. By certain generic
results on vertex-partitioning [1, 6], $k$-Partition$(v)$ in general graphs is
NP-hard for all $k\geq 2$ and $v\geq 1$.

Broersma et al. [5, Theorem 5.4] proved that for any fixed $k$, deciding
whether an interval graph with $n$ vertices has subchromatic number at most
$k$ admits an algorithm running in $O(k\cdot n^{2k+1})$ time. In other words,
they presented an $O(k\cdot n^{2k+1})$-time algorithm for $k$-Partition$(1)$
in interval graphs.

Gandhi et al. [8] noted that the two results [5, Lemma 2.4 and Theorem 5.4]
together imply an $n^{O(\log n)}$-time exact algorithm for subcoloring
interval graphs, and hence this problem is unlikely to be NP-hard.
Nevertheless, they presented a $3$-approximation algorithm for subcoloring
interval graphs. In addition, they presented a $6$-approximation algorithm for
partitioning an interval graph into the minimum number of proper interval
graphs. In other words, they obtained a $3$-approximation for Min-
Partition$(1)$, and a $6$-approximation for Min-Partition$(2)$, in interval
graphs.

We present a simple approximation algorithm for Min-Partition$(v)$ in interval
graphs for all $v\geq 1$:

######  Theorem 4.

Min-Partition$(v)$ in interval graphs admits a polynomial-time approximation
algorithm with ratio $3$ for $1\leq v\leq 2$, and with ratio $2$ for $v\geq
3$.

##  2 Preliminaries

Interval graphs can be recognized in linear time [10]. Henceforth when we
refer to an interval graph, we assume that an interval representation of the
graph is readily available when needed, and we refer to an interval graph and
its interval representation interchangeably.

An _independent set_ (respectively, a _clique_) is a set of pairwise non-
adjacent (respectively, adjacent) vertices in a graph. Besides the claw number
$\psi(G)$ introduced earlier, there are two other common parameters for a
graph $G$:

  * •

the _independence number_ $\alpha(G)$ is the maximum number of vertices in an
independent set in $G$,

  * •

the _vertex-clique-partition number_ $\vartheta(G)$ is the minimum number of
parts in a vertex partition of $G$ into cliques.

It is easy to see that $\psi(G)\leq\alpha(G)\leq\vartheta(G)$ for any graph
$G$. Indeed, if $G$ is an interval graph, then $\alpha(G)=\vartheta(G)$ [10].
We next sketch a simple constructive proof of the equality
$\alpha(G)=\vartheta(G)$ for an interval graph $G$. Let $\mathcal{I}$ be a
family of open intervals whose intersection graph is $G$. Without loss of
generality, assume that all endpoints of intervals in $\mathcal{I}$ are
integers. Then we can find an independent set and a vertex clique partition at
the same time by a standard _sweepline algorithm_ as follows:

> Initialize $\mathcal{I}^{\prime}\leftarrow\mathcal{I}$ and $i\leftarrow 1$.
> While $\mathcal{I}^{\prime}$ is not empty, let $T_{i}=(l_{i},r_{i})$ be an
> interval in $\mathcal{I}^{\prime}$ whose right endpoint $r_{i}$ is minimum,
> let $\mathcal{I}^{\prime}_{i}$ (respectively, $\mathcal{I}_{i}$) be the
> subfamily of intervals in $\mathcal{I}^{\prime}$ (respectively,
> $\mathcal{I}$) that contain the subinterval $S_{i}=(r_{i}-1,r_{i})$ of
> $T_{i}$, then update
> $\mathcal{I}^{\prime}\leftarrow\mathcal{I}^{\prime}\setminus\mathcal{I}^{\prime}_{i}$
> and $i\leftarrow i+1$.

Let $j$ be the number of rounds that the sweepline algorithm runs until
$\mathcal{I}^{\prime}$ is empty. Then for $1\leq i\leq j$, $S_{i}\subseteq
T_{i}\in\mathcal{I}^{\prime}_{i}\subseteq\mathcal{I}_{i}$. Moreover, the $j$
intervals $T_{i}$ correspond to an independent set in $G$, and the $j$
subfamilies $\mathcal{I}^{\prime}_{i}$ correspond to a partition of the
vertices of $G$ into cliques. Thus $\alpha(G)=\vartheta(G)$.

For a graph $G$ and $v\geq 1$, let $\kappa(G,v)$ be the smallest number of
induced subgraphs in a vertex partition of $G$ such that each subgraph has
claw number at most $v$.

######  Lemma 1.

For $k\geq 1$ and $v\geq 1$, any interval graph $G$ with
$\vartheta(G)\leq(v+1)^{k}-1$ satisfies $\kappa(G,v)\leq k$.

###### Proof.

Fix any $v\geq 1$. We prove the lemma by induction on $k$. For the base case
when $k=1$, any interval graph $G$ with $\vartheta(G)\leq(v+1)^{1}-1=v$ has
$\psi(G)\leq\vartheta(G)\leq v$ and hence $\kappa(G,v)\leq 1$. Now let $k\geq
2$, and let $G$ be an interval graph with $\vartheta(G)\leq(v+1)^{k}-1$. We
next show that $G$ admits a vertex partition into $k$ induced subgraphs with
claw number at most $v$.

Run the sweepline algorithm on an interval representation $\mathcal{I}$ of $G$
to obtain $j=\vartheta(G)$ cliques $\mathcal{I}_{i}$, $1\leq i\leq j$, such
that $\mathcal{I}=\cup_{i}\,\mathcal{I}_{i}$. Let $t=(v+1)^{k}-1$ and
$s=(v+1)^{k-1}-1$. Then $j\leq t=(v+1)(s+1)-1=v(s+1)+s$. Let $\mathcal{J}$ be
the union of all subfamilies $\mathcal{I}_{i}$ with $i\bmod(s+1)=0$. The
subgraph of $G$ represented by $\mathcal{J}$ has vertex-clique-partition
number at most $v$, and hence claw number at most $v$ too.

Each connected component in the subgraph of $G$ represented by
$\mathcal{I}\setminus\mathcal{J}$ has vertex-clique-partition number at most
$s=(v+1)^{k-1}-1$, and hence admits a vertex partition into $k-1$ induced
subgraphs with claw number at most $v$, by the induction hypothesis. Then by
disjoint union, the subgraph of $G$ represented by
$\mathcal{I}\setminus\mathcal{J}$ also admits a vertex partition into $k-1$
induced subgraphs with claw number at most $v$. Thus $\kappa(G,v)\leq
1+(k-1)=k$. ∎

To prove that their upper bound on subchromatic numbers of interval graphs is
best possible, Broersma et al. [5, Lemma 2.4] showed that for any $k\geq 1$,
there is an interval graph $G_{k}$ with $2^{k}-1$ vertices and subchromatic
number $k$. Such graphs were later used by Gandhi et al. [8] as a lower bound
in their $3$-approximation algorithm for subcoloring interval graphs; they
refer to $G_{k}$ as $BC(k)$ and call them binary cliques. Similarly, Gardi [9,
Lemma 2.1] showed that for any $k\geq 1$, there is an interval graph $H_{k}$
with $(3^{k}-1)/2$ vertices that admits no vertex partition into less than $k$
proper interval graphs.

$G_{k}$ and $H_{k}$ for $k\geq 1$ are recursively constructed as follows:
$G_{1}$ (respectively, $H_{1}$) is just a single vertex. For $k\geq 2$,
$G_{k}$ (respectively, $H_{k}$) consists of a new vertex connected to all
vertices of $2$ (respectively, $3$) disjoint copies of $G_{k-1}$
(respectively, $H_{k-1}$).

$G_{k}$ and $H_{k}$ for $k\geq 1$ can be generalized to $A_{k,v}$ for $k\geq
1$ and $v\geq 1$: $A_{1,v}$ is just a single vertex. For $k\geq 2$, $A_{k,v}$
consists of a new vertex connected to all vertices of $v+1$ disjoint copies of
$A_{k-1,v}$. Then $G_{k}=A_{k,1}$ and $H_{k}=A_{k,2}$. Refer to Figure 1 for
an illustration of $H_{3}=A_{3,2}$.

Figure 1: An interval representation of $H_{3}=A_{3,2}$.

It is easy to see that for $k\geq 1$ and $v\geq 1$, $A_{k,v}$ is an interval
graph with $\sum_{i=0}^{k-1}(v+1)^{i}=((v+1)^{k}-1)/v$ vertices, and
$\alpha(A_{k,v})=\vartheta(A_{k,v})=(v+1)^{k-1}$. Also, for $k\geq 2$ and
$v\geq 1$, $\psi(A_{k,v})=(v+1)^{k-1}$.

######  Lemma 2.

For $k\geq 2$ and $v\geq 1$, $\kappa(A_{k,v},v)=k$.

###### Proof.

Fix any $v\geq 1$. Since $\vartheta(A_{k,v})=(v+1)^{k-1}\leq(v+1)^{k}-1$, it
follows by Lemma 1 that $\kappa(A_{k,v},v)\leq k$. We next show that
$\kappa(A_{k,v},v)\geq k$ by induction on $k$. For the base case when $k=2$,
$A_{2,v}$ is simply $K_{1,v+1}$, and hence admits no vertex partition into
less than $2$ induced subgraphs with claw number at most $v$. Now proceed to
the inductive step when $k\geq 3$.

Consider any vertex partition of $A_{k,v}$ into induced subgraphs with claw
number at most $v$. Recall that $A_{k,v}$ consists of a new vertex connected
to $v+1$ disjoint copies of $A_{k-1,v}$. To avoid a star $K_{1,v+1}$ forming
around the new vertex, the subgraph that includes it can include vertices from
at most $v$ copies of $A_{k-1,v}$, and hence must miss one copy of $A_{k-1,v}$
entirely. By the induction hypothesis, this copy of $A_{k-1,v}$ admits no
vertex partition into less than $k-1$ induced subgraphs with claw number at
most $v$. It follows that $A_{k,v}$ admits no vertex partition into less than
$k$ induced subgraphs with claw number at most $v$. Thus
$\kappa(A_{k,v},v)\geq k$. ∎

Note that for $k\geq 1$ and $v\geq 1$, the interval graph $A_{k+1,v}$
satisfies $\vartheta(A_{k+1,v})=(v+1)^{k}$ and $\kappa(A_{k+1,v},v)=k+1$. This
shows that the bound in Lemma 1 is best possible.

##  3 $\mu(k,v)$ and $\kappa(n,v)$

In this section we prove Theorem 1 and Corollary 1.

For a family $\mathcal{I}$ of intervals, denote by $|\mathcal{I}|$ the number
of intervals in $\mathcal{I}$. We first prove a technical lemma:

######  Lemma 3.

For $n\geq s\geq 1$, the vertex set of any interval graph $G$ with $n$
vertices can be partitioned into $2r+1$ subsets for some $r\geq 0$, including
$X_{i}$ and $Y_{i}$ for $1\leq i\leq r$, and $Z$, such that

  1. 1.

Vertices from different subsets among $X_{i}$ and $Z$ are non-adjacent in $G$.

  2. 2.

Vertices in each subset $Y_{i}$ are pairwise adjacent in $G$.

  3. 3.

$|Z|\leq|X_{i}|=s<|X_{i}|+|Y_{i}|$.

###### Proof.

For any family $\mathcal{Z}$ of intervals, and for $p\leq q$, denote by
$\mathcal{Z}(p,q)$ the subfamily of intervals in $\mathcal{Z}$ that are
contained in the interval $(p,q)$.

Obtain an interval representation $\mathcal{I}$ of $G$ with integer endpoints.
Let $a$ be the leftmost endpoint, and $c$ the rightmost endpoint, of the
intervals in $\mathcal{I}$.

Initialize $\mathcal{Z}\leftarrow\mathcal{I}$ and $i\leftarrow 1$. While
$|\mathcal{Z}|>s$, let $b$ be the smallest integer in $(a,c]$ such that
$|\mathcal{Z}(a,b-1)|\leq s<|\mathcal{Z}(a,b)|$, let $\mathcal{X}_{i}$ be any
subfamily of $s$ intervals in $\mathcal{Z}$ such that
$\mathcal{Z}(a,b-1)\subseteq\mathcal{X}_{i}\subset\mathcal{Z}(a,b)$, let
$\mathcal{Y}_{i}$ be
$\mathcal{Z}\setminus(\mathcal{X}_{i}\cup\mathcal{Z}(b,c))$, then update
$\mathcal{Z}\leftarrow\mathcal{Z}\setminus(\mathcal{X}_{i}\cup\mathcal{Y}_{i})$
and $i\leftarrow i+1$.

Let $r\geq 0$ be the number of such partitioning rounds until
$|\mathcal{Z}|\leq s$. Then $\mathcal{I}$ is partitioned into $2r+1$
subfamilies, including $\mathcal{X}_{i}$ and $\mathcal{Y}_{i}$ for $1\leq
i\leq r$, and a (possibly empty) subfamily $\mathcal{Z}$ in the end. The
following three properties can be easily verified:

  1. 1.

Intervals from different subfamilies among $\mathcal{X}_{i}$ and $\mathcal{Z}$
do not intersect.

  2. 2.

Intervals in each subfamily $\mathcal{Y}_{i}$ pairwise intersect.

  3. 3.

$|\mathcal{Z}|\leq|\mathcal{X}_{i}|=s<|\mathcal{X}_{i}|+|\mathcal{Y}_{i}|$.

Let $X_{i}$, $Y_{i}$, and $Z$ be the subsets of vertices of $G$ represented by
intervals in $\mathcal{X}_{i}$, $\mathcal{Y}_{i}$, and $\mathcal{Z}$,
respectively. Then the proof is complete. ∎

We now prove Theorem 1 that $\mu(k,v)=((v+1)^{k+1}-(v+1))/v$ for $k\geq 1$ and
$v\geq 1$. Fix $v\geq 1$, and let $n_{k}=((v+1)^{k+1}-(v+1))/v$.

Recall Lemma 2 that for $k\geq 1$ and $v\geq 1$, the interval graph
$A_{k+1,v}$ has $((v+1)^{k+1}-1)/v$ vertices, and satisfies
$\kappa(A_{k+1,v},v)=k+1$. This implies the upper bound of
$\mu(k,v)\leq((v+1)^{k+1}-1)/v-1=n_{k}$. In the following we prove the
matching lower bound of $\mu(k,v)\geq n_{k}$ by induction on $k$.

For the base case when $k=1$, we have $n_{1}=((v+1)^{1+1}-(v+1))/v=v+1$. Any
interval graph with at most $v+1$ vertices obviously has claw number at most
$v$. Thus $\mu(1,v)\geq n_{1}$. Now proceed to the inductive step when $k\geq
2$, and let $G$ be an interval graph with at most $n_{k}$ vertices.

Apply Lemma 3 with $s=n_{k-1}$ to partition the vertex set of $G$ into $2r+1$
subsets, $X_{i}$ and $Y_{i}$ for $1\leq i\leq r$, and $Z$. Since
$n_{k}=(v+1)(n_{k-1}+1)=(v+1)(s+1)$, we have $1\leq r\leq v+1$. Consider two
cases:

  * •

$r\leq v$. Note that $|X_{i}|=n_{k-1}$ for $1\leq i\leq r$, and that $|Z|\leq
n_{k-1}$. By the induction hypothesis, any interval graph with at most
$n_{k-1}$ vertices admits a vertex partition into $k-1$ induced subgraphs with
claw number at most $v$. Then by disjoint union, the subgraph of $G$ induced
by all vertices in the $r$ subsets $X_{i}$ and the subset $Z$ admits a vertex
partition into $k-1$ subgraphs with claw number at most $v$. On the other
hand, the subgraph of $G$ induced by vertices in the $r$ subsets $Y_{i}$ is
the union of $r$ cliques, and has vertex-clique-partition number at most $r$,
and hence has claw number at most $r\leq v$.

  * •

$r=v+1$. Then we must have $|X_{i}|=n_{k-1}$ and $|Y_{i}|=1$ for $1\leq i\leq
v+1$, and $|Z|=0$. The subgraph of $G$ induced by all vertices in the $r$
subsets $X_{i}$ admits a vertex partition into $k-1$ subgraphs with claw
number at most $v$. On the other hand, the subgraph of $G$ induced by the
$v+1$ vertices in the $v+1$ subsets $Y_{i}$ clearly has claw number at most
$v$ too.

In both cases, $G$ admits a vertex partition into $k$ induced subgraphs with
claw number at most $v$. This completes the proof of Theorem 1.

We next prove Corollary 1 that $\kappa(n,v)=\lfloor\log_{v+1}(nv+1)\rfloor$
for $n\geq 1$ and $v\geq 1$. Fix any $v\geq 1$.

For $1\leq n\leq v+1$, we have $v+1\leq nv+1<(v+1)^{2}$, and hence
$\lfloor\log_{v+1}(nv+1)\rfloor=1$. It is clear that $\kappa(n,v)=1$ for this
case.

Now fix $n\geq v+2$. Then $nv+1\geq(v+1)^{2}$ and hence
$\lfloor\log_{v+1}(nv+1)\rfloor\geq 2$. Let
$k=\lfloor\log_{v+1}(nv+1)\rfloor$. Then $n\geq((v+1)^{k}-1)/v$. By Lemma 2,
the interval graph $A_{k,v}$ with $((v+1)^{k}-1)/v$ vertices satisfies
$\kappa(A_{k,v},v)=k$. Thus $\kappa(n,v)\geq\kappa(((v+1)^{k}-1)/v,v)\geq k$.

For the other direction, let $\kappa=\kappa(n,v)$. Then by definition of
$\mu$, we have $n\geq\mu(\kappa-1,v)+1$. By Theorem 1,
$\mu(\kappa-1,v)=((v+1)^{\kappa}-(v+1))/v$. Thus $n\geq((v+1)^{\kappa}-1)/v$.
It follows that $\kappa\leq\lfloor\log_{v+1}(nv+1)\rfloor=k$. This completes
the proof of Corollary 1.

##  4 $\check{\mu}(k,v)$ and $\check{\kappa}(w,v)$

In this section we prove Theorem 2 and Corollary 2.

We first prove Theorem 2. Fix $k\geq 2$ and $v\geq 1$. Recall Lemma 2 that the
interval graph $A_{k+1,v}$ with claw number $(v+1)^{k}$ satisfies
$\kappa(A_{k+1,v},v)=k+1$. This implies the upper bound of
$\check{\mu}(k,v)\leq(v+1)^{k}-1$.

Write $w_{1}=(v+1)^{k-1}/2$, $w_{2}=2(v+1)^{k-1}/3$, and
$w_{3}=(v-2)(v+1)^{k-1}$. Let $G$ be an interval graph with claw number $w\leq
w_{1}$ when $v=1$, $w\leq w_{2}$ when $v=2$, and $w\leq w_{3}$ when $v\geq 3$.
In the following, we obtain a vertex partition of $G$ into $k$ induced
subgraphs with claw number at most $v$, hence proving the lower bounds
$\check{\mu}(k,v)\geq w_{1}$ when $v=1$, $\check{\mu}(k,v)\geq w_{2}$ when
$v=2$, and $\check{\mu}(k,v)\geq w_{3}$ when $v\geq 3$.

Let $\mathcal{I}$ be an interval representation of $G$ with integer endpoints.
Let $j=\vartheta(G)$. Run the sweepline algorithm to obtain an independent set
of $j$ intervals $T_{i}$ in $\mathcal{I}$, and a vertex covering of
$\mathcal{I}$ by $j$ cliques $\mathcal{I}_{i}$, where
$T_{i}\in\mathcal{I}_{i}$ for $1\leq i\leq j$.

Let $s=2w$ when $v=1$, $s=\lceil 3w/2\rceil$ when $v=2$, and $s=\lceil
w/(v-2)\rceil$ when $v\geq 3$. Then for all $v\geq 1$, $s\leq(v+1)^{k-1}$. Let
$\mathcal{J}$ be the union of all subfamilies $\mathcal{I}_{i}$ with $i\bmod
s=0$. Then each connected component in the graph represented by
$\mathcal{I}\setminus\mathcal{J}$ has vertex-clique-partition number at most
$s-1\leq(v+1)^{k-1}-1$, and hence admits a vertex partition into $k-1$ induced
subgraphs with claw number at most $v$, by Lemma 1. Then by disjoint union,
the graph represented $\mathcal{I}\setminus\mathcal{J}$ also admits a vertex
partition into $k-1$ induced subgraphs with claw number at most $v$. It
remains to show that the graph represented by $\mathcal{J}$ has claw number at
most $v$.

Suppose for contradiction that the graph represented by $\mathcal{J}$ has claw
number at least $v+1$. Let $C$ and $L_{1},\ldots,L_{v+1}$ be intervals
representing the center and the $v+1$ leaves of a star $K_{1,v+1}$ in the
graph, where the $v+1$ intervals $L_{1},\ldots,L_{v+1}$ are ordered from left
to right. We now proceed in three different ways depending on the value of
$v$:

  1. 1.

$v=1$. Either $L_{1}$ and $C$, or $C$ and $L_{2}$, are two intervals from two
subfamilies $\mathcal{I}_{ps}$ and $\mathcal{I}_{qs}$ with $q-p\geq 1$. The
union of the two intervals is a contiguous interval that intersects all
intervals in $qs-ps+1$ consecutive subfamilies $\mathcal{I}_{i}$, $ps\leq
i\leq qs$, which include the $qs-ps+1$ disjoint intervals $T_{i}$, $ps\leq
i\leq qs$. Then one of these two intervals intersects at least $\lceil(qs-
ps+1)/2\rceil\geq\lceil(s+1)/2\rceil=\lceil(2w+1)/2\rceil=w+1$ disjoint
intervals $T_{i}$.

  2. 2.

$v=2$. $L_{1}$ and $L_{3}$ are from two subfamilies $\mathcal{I}_{ps}$ and
$\mathcal{I}_{qs}$ with $q-p\geq 2$. The union of $L_{1}$, $C$, and $L_{3}$ is
a contiguous interval that intersects all intervals in $qs-ps+1$ consecutive
subfamilies $\mathcal{I}_{i}$, $ps\leq i\leq qs$. One of these three intervals
intersects at least $\lceil(qs-
ps+1)/3\rceil\geq\lceil(2s+1)/3\rceil\geq\lceil(3w+1)/3\rceil=w+1$ disjoint
intervals $T_{i}$.

  3. 3.

$v\geq 3$. $L_{2}$ and $L_{v}$ are from two subfamilies $\mathcal{I}_{ps}$ and
$\mathcal{I}_{qs}$ with $q-p\geq v-2$. $C$ intersects all intervals in $qs-
ps+1$ consecutive subfamilies $\mathcal{I}_{i}$, $ps\leq i\leq qs$. Note that
$qs-ps+1\geq(v-2)s+1\geq w+1$. Thus $C$ intersects at least $w+1$ disjoint
intervals $T_{i}$.

In each of the three cases, we can find a star $K_{1,w+1}$ in $G$ represented
by some interval in $\mathcal{J}$ intersecting $w+1$ disjoint intervals
$T_{i}\in\mathcal{I}_{i}$, a contradiction to our assumption that $G$ has claw
number $w$. Thus the graph represented by $\mathcal{J}$ must have claw number
at most $v$. This completes the proof of Theorem 2.

We next prove the bounds on $\check{\kappa}(w,v)$ in Corollary 2 for $w>v\geq
1$. Let $k=\lfloor\log_{v+1}w\rfloor+1$. Then $w\geq(v+1)^{k-1}$ and $k\geq
2$. By Lemma 2, the interval graph $A_{k,v}$ with claw number $(v+1)^{k-1}$
satisfies $\kappa(A_{k,v},v)=k$. Thus we have the lower bound
$\check{\kappa}(w,v)\geq\check{\kappa}((v+1)^{k-1},v)\geq k$.

For the other direction, let $\check{\kappa}=\check{\kappa}(w,v)$, where
$\check{\kappa}\geq 2$. Then by definition of $\check{\mu}$, we have
$w\geq\check{\mu}(\check{\kappa}-1,v)+1$. By the lower bounds in Theorem 2, we
have $w\geq(v+1)^{\check{\kappa}-2}/2+1$ when $v=1$, $w\geq
2(v+1)^{\check{\kappa}-2}/3+1$ when $v=2$, and
$w\geq(v-2)(v+1)^{\check{\kappa}-2}+1$ when $v\geq 3$. Correspondingly,

  * •

when $v=1$,
$\check{\kappa}(w,v)\leq\lfloor\log_{v+1}{2(w-1)}\rfloor+2=\lfloor\log_{v+1}{(w-1)}\rfloor+3\leq\lfloor\log_{v+1}{w}\rfloor+3$,

  * •

when $v=2$,
$\check{\kappa}(w,v)\leq\lfloor\log_{v+1}{3(w-1)/2}\rfloor+2=\lfloor\log_{v+1}{(w-1)/2}\rfloor+3\leq\lfloor\log_{v+1}{w}\rfloor+3$,

  * •

when $v\geq 3$,
$\check{\kappa}(w,v)\leq\lfloor\log_{v+1}{(w-1)/(v-2)}\rfloor+2\leq\lfloor\log_{v+1}{w}\rfloor+2$.

Thus we have the upper bounds on $\check{\kappa}(w,v)$. This completes the
proof of Corollary 2.

##  5 $\check{\kappa}(w,v)$ for small $w$ and $v$

In this section we prove Theorem 3 that $\check{\kappa}(2,1)=2$,
$\check{\kappa}(3,1)=3$, $\check{\kappa}(3,2)=2$,
$\check{\kappa}(4,2)=\check{\kappa}(5,2)=\check{\kappa}(6,2)=3$, and
$\check{\kappa}(5,3)=2$.

We first prove that $\check{\kappa}(2,1)=2$ and $\check{\kappa}(3,1)=3$.
Recall [3, Theorem 4] that $\check{\kappa}(w,1)\leq w$ for any $w\geq 1$. In
particular, $\check{\kappa}(2,1)\leq 2$ and $\check{\kappa}(3,1)\leq 3$. From
the other direction, it is clear that $\check{\kappa}(w,v)\geq 2$ for any
$w>v\geq 1$. Thus $\check{\kappa}(2,1)=2$. The following lemma implies that
$\check{\kappa}(3,1)\geq 3$, and hence we have $\check{\kappa}(3,1)=3$.

######  Lemma 4.

Let $\mathcal{J}_{3}$ be the set of $12$ open intervals with lengths $1$, $2$,
and $3$, and with integer endpoints between $0$ and $5$. Then the interval
graph represented by $\mathcal{J}_{3}$ has claw number $3$ and admits a vertex
partition into three subgraphs with claw number at most $1$, but it admits no
vertex partition into two subgraphs with claw number at most $1$.

###### Proof.

The interval graph represented by $\mathcal{J}_{3}$, with maximum interval
length $3$, clearly has claw number $3$. Moreover, it admits a vertex
partition, by left endpoint modulo $3$, into three subgraphs with claw number
at most $1$ (that is, three cluster graphs). To show that the graph admits no
vertex partition into two subgraphs with claw number at most $1$, we suppose
the contrary and color each interval in $\mathcal{J}_{3}$ either white or
black according to such a partition, then find three intervals of the same
color that represent $K_{1,2}$ to reach a contradiction.

Figure 2: Intervals from $\mathcal{J}_{3}$ for the three cases in the proof of
Lemma 4.

Refer to Figure 2. Consider three cases:

  1. 1.

$\mathcal{J}_{3}$ contains three consecutive unit intervals among which the
left and the right have opposite colors. Let $(a,a+1)$, $(a+1,a+2)$,
$(a+2,a+3)$ be the three unit intervals. Consider also the two length-$2$
intervals $(a,a+2)$ and $(a+1,a+3)$, and the length-$3$ interval $(a,a+3)$. By
symmetry, we can assume without loss of generality that $(a,a+1)$ and
$(a+1,a+2)$ are white, and $(a+2,a+3)$ is black. Then both $(a,a+2)$ and
$(a,a+3)$ must be black to avoid forming a white star $K_{1,2}$ with $(a,a+1)$
and $(a+1,a+2)$. But then $(a,a+3)$, $(a,a+2)$, $(a+2,a+3)$ form a black star
$K_{1,2}$.

  2. 2.

The five unit intervals in $\mathcal{J}_{3}$ all have the same color. Consider
any four consecutive unit intervals, say, $(a,a+1)$, $(a+1,a+2)$, $(a+2,a+3)$,
$(a+3,a+4)$. Assume without loss of generality that they are all white.
Consider also the three length-$2$ intervals $(a,a+2)$, $(a+1,a+3)$,
$(a+2,a+4)$. Either one of them is white, forming a white star $K_{1,2}$ with
two unit intervals, or all of them are black, forming a black star $K_{1,2}$
by themselves.

  3. 3.

The five unit intervals in $\mathcal{J}_{3}$ have alternating colors. Let
$(a,a+1)$, $(a+1,a+2)$, $(a+2,a+3)$, $(a+3,a+4)$, $(a+4,a+5)$ be the five unit
intervals. Assume without loss of generality that $(a,a+1)$, $(a+2,a+3)$,
$(a+4,a+5)$ are white, $(a+1,a+2)$ and $(a+3,a+4)$ are black. Then the
length-$3$ interval $(a,a+3)$ must be black to avoid forming a white star
$K_{1,2}$ with $(a,a+1)$ and $(a+2,a+3)$. Similarly, the length-$3$ interval
$(a+2,a+5)$ must be black to avoid forming a white star $K_{1,2}$ with
$(a+2,a+3)$ and $(a+4,a+5)$. Then the two intervals $(a,a+3)$ and $(a+2,a+5)$,
together with either $(a+1,a+2)$ or $(a+3,a+4)$, form a black star $K_{1,2}$.

In each case, there are three intervals in $\mathcal{J}_{3}$ representing a
monochromatic star $K_{1,2}$. ∎

We next prove that $\check{\kappa}(3,2)=2$ and
$\check{\kappa}(4,2)=\check{\kappa}(5,2)=\check{\kappa}(6,2)=3$. By our upper
bound of $\check{\kappa}(w,v)\leq\lfloor\log_{v+1}3(w-1)/2\rfloor+2$ for
$w>v=2$ in Corollary 2, we have $\check{\kappa}(6,2)\leq 3$. On the other
hand, it is clear that $\check{\kappa}(3,2)\geq 2$. Thus

$2\leq\check{\kappa}(3,2)\leq\check{\kappa}(4,2)\leq\check{\kappa}(5,2)\leq\check{\kappa}(6,2)\leq
3.$ (1)

As a warm-up exercise, we first prove the following lemma which implies that
$\check{\kappa}(6,2)\geq 3$, and hence $\check{\kappa}(6,2)=3$.

######  Lemma 5.

Let $\mathcal{J}_{6}$ be the family of $24$ open intervals with lengths $1$,
$3$, $5$, and $6$ as illustrated in Figure 3. Then the interval graph
represented by $\mathcal{J}_{6}$ has claw number $6$ and admits a vertex
partition into three subgraphs with claw number at most $2$, but it admits no
vertex partition into two subgraphs with claw number at most $2$.

Figure 3: The family $\mathcal{J}_{6}$ of $24$ intervals includes $13$, $1$,
$2$, and $8$ intervals with lengths $1$, $3$, $5$, and $6$, respectively.

###### Proof.

The interval graph represented by $\mathcal{J}_{6}$ clearly has claw number
$6$, and admits a vertex partition, by lengths
$\\{1\\}\cup\\{3\\}\cup\\{5,6\\}$, into three subgraphs with claw number at
most $2$. Suppose for contradiction that it admits a vertex partition into two
subgraphs with claw number at most $2$. Then any two intervals in
$\mathcal{J}_{6}$ containing five unit intervals in their intersection must
have the same color, because otherwise one of them would have the same color
as three of the five unit intervals, forming a monochromatic star $K_{1,3}$.
Consequently all length-$5$ and length-$6$ intervals must have the same color.

Consider the length-$3$ interval in the middle and the three unit intervals
contained in it. If any of these four intervals has the same color as the
length-$5$ and length-$6$ intervals, then it would form a monochromatic star
together with the two length-$5$ intervals and a length-$6$ interval that
intersects all of them. Otherwise, these four intervals in the middle would
have the same color, and would form a monochromatic star $K_{1,3}$ by
themselves. In both cases, we reach a contradiction. ∎

The next lemma implies that $\check{\kappa}(5,2)\geq 3$, and hence
$\check{\kappa}(5,2)=3$.

######  Lemma 6.

Let $\mathcal{J}_{5}$ be the family of open intervals with lengths $1$, $3$,
and $5$, and with integer endpoints between $0$ and $79$. The interval graph
represented by $\mathcal{J}_{5}$ has claw number $5$ and admits a vertex
partition into three subgraphs with claw number at most $2$, but it admits no
vertex partition into two subgraphs with claw number at most $2$.

###### Proof.

The interval graph represented by $\mathcal{J}_{5}$ clearly has claw number
$5$, and admits a vertex partition (by lengths) into three subgraphs with claw
number at most $2$. To show that the graph admits no vertex partition into two
subgraphs with claw number at most $2$, we suppose the contrary and color each
interval in $\mathcal{J}_{5}$ either white or black according to such a
partition, then find four intervals of the same color that represent a star
$K_{1,3}$ to reach a contradiction.

Figure 4: A length-$5$ interval and eight neighbors in $\mathcal{J}_{5}$.

Consider any subset of nine intervals in $\mathcal{J}_{5}$ whose lengths and
relative positions are as illustrated in Figure 4. Focus on the length-$5$
interval in the middle, and consider the other eight intervals as its
neighbors. We refer to the length-$5$ interval on the left and the leftmost
unit interval as the _left neighbors_ , the length-$5$ interval on the right
and the rightmost unit interval as the _right neighbors_ , the length-$3$
interval and the three unit intervals in the middle as the _middle neighbors_
, respectively, of the length-$5$ interval in the middle. If the length-$5$
interval in the middle has the same color as both a left neighbor and a right
neighbor, then to avoid a monochromatic star $K_{1,3}$ it cannot have the same
color as any of its middle neighbors. But then the four middle neighbors would
have the same color, and form a monochromatic star $K_{1,3}$ by themselves.
Thus we have the following property:

> No length-$5$ interval in $\mathcal{J}_{5}$ can have both a left neighbor
> and a right neighbor of the same color as itself.

Partition the unit intervals in $\mathcal{J}_{5}$ into four _groups_ according
to their left endpoints modulo $4$. We say that two unit intervals in the same
group are _$4$ -adjacent_ if their left endpoints differ by exactly $4$. For
any two $4$-adjacent unit intervals $A$ and $B$ in $\mathcal{J}_{5}$, denote
by $AB$ the unique length-$5$ interval in $\mathcal{J}_{5}$ that contains
them.

Figure 5: A chain of consecutive $4$-adjacent unit intervals $P,Q,R,S,T,U,V$.

Consider a chain of $4$-adjacent unit intervals from the same group in
$\mathcal{J}_{5}$, in the middle row of the three rows of intervals
illustrated in Figure 5. Suppose that both $R$ and $S$ are white. Then $RS$
must be black. Then $QR$ and $ST$ cannot be both black. Without loss of
generality, assume that $QR$ is white. Then $Q$ is black, and so is $PQ$. Then
the argument repeats as the chain extends further to the left with alternating
colors: $P$ is white, the unit interval that is $4$-adjacent to $P$ on the
left, if any, is black, and so on. Now consider $ST$. If $ST$ is white, then
the situation is symmetric to the case that $QR$ is white, with respect to the
starting interval $RS$. If $ST$ is black, then $T$ is white and so is $TU$.
Then the argument repeats as the chain extends further to the right with
alternating colors, for $U$ and $V$ and so on.

In summary, in the chain of $4$-adjacent unit intervals from each group, there
is at most one monochromatic subchain of two or more consecutive $4$-adjacent
unit intervals of the same color, and moreover the length of such a
monochromatic subchain, if it exists, is either two or three. For each such
monochromatic subchain, if its length is two, mark any one of the two unit
intervals as a hole, or else if its length is three, mark the unit interval in
the middle (for example, $S$ among $R,S,T$ as in Figure 5) as a hole. Then
there are at most $h\leq 4$ holes from the four groups, and they separate the
other $79-h$ unit intervals in $\mathcal{J}_{5}$ into at most $h+1$ contiguous
_blocks_. The longest block has length at least $(79-4)/(4+1)=15$. Within each
block, every two $4$-adjacent unit intervals have different colors.

Encode white as $0$ and black as $1$. Then the colors of all unit intervals in
each block form a periodic binary string of period $8$, whose periodic pattern
is the concatenation of a $4$-bit binary string and its complement. There are
$16$ periodic patterns:

$\displaystyle 00001111\quad 00011110\quad 00101101\quad 00111100\quad
01001011\quad 01011010\quad 01101001\quad 01111000$ $\displaystyle
10000111\quad 10010110\quad 10100101\quad 10110100\quad 11000011\quad
11010010\quad 11100001\quad 11110000$

It is easy to verify that each of the $16$ patterns is a rotation of either
$10100101$ or $11000011$. Since the longest block has length at least
$15=2\cdot 8-1$, the binary string corresponding to this block must contain
either $10100101$ or $11000011$ as a substring.

Figure 6: The colors of all unit intervals in each block form a periodic
binary string. Left: two length-$5$ intervals and eight unit intervals for the
periodic pattern $10100101$. Right: two length-$5$ intervals and eight unit
intervals for the periodic pattern $11000011$.

Refer to Figure 6 for the two cases. Consider the two length-$5$ intervals
containing the five unit intervals corresponding to the first five bits and
the last five bits, respectively, of this substring. Since each of them
contains three white unit intervals, they must both be black to avoid forming
a white star $K_{1,3}$. But then the two black length-$5$ intervals, and the
two black unit intervals contained by either of them, would form a black star
$K_{1,3}$. ∎

The next lemma implies that $\check{\kappa}(4,2)\geq 3$, and hence
$\check{\kappa}(4,2)=3$.

######  Lemma 7.

Let $\mathcal{J}_{4}$ be the family of open intervals with integer lengths
between $2$ and $7$, and with integer endpoints between $0$ and $21$. The
interval graph represented by $\mathcal{J}_{4}$ has claw number $4$ and admits
a vertex partition into three subgraphs with claw number at most $2$, but it
admits no vertex partition into two subgraphs with claw number at most $2$.

###### Proof.

The interval graph represented by $\mathcal{J}_{4}$ clearly has claw number
$4$, since the maximum length $7$ is only one plus three times the minimum
length $2$. By the upper bound for the $v=2$ case of Corollary 2, we have
$\check{\kappa}(4,2)\leq 3$, and hence the graph represented by
$\mathcal{J}_{4}$ admits a vertex partition into three subgraphs with claw
number at most $2$. We say that a $2$-partition of a family of intervals is
_bad_ if there are four intervals representing a star $K_{1,3}$ in the same
part, and say that it is _good_ otherwise. Assisted by a computer program, we
next show that $\mathcal{J}_{4}$ admits no good $2$-partition.

Note that $\mathcal{J}_{4}$ contains exactly $22-\ell$ intervals of each
length $\ell$, $2\leq\ell\leq 7$. The total number of intervals in
$\mathcal{J}_{4}$ is $n=20+19+18+17+16+15=105$. A brute-force algorithm that
enumerates all $2^{105}$ $2$-partitions of $\mathcal{J}_{4}$ is obviously too
slow, but we can speed it up by a standard branch-and-bound technique.

The algorithm works as follows. Sort the intervals in $\mathcal{J}_{4}$ by
increasing right endpoint, breaking ties by decreasing left endpoint. Then
call the following recursive function with a partial $2$-partition of
$\mathcal{J}_{4}$ with the first interval in the first part.

Given a good partial $2$-partition of the first $i$ intervals in
$\mathcal{J}_{4}$, the recursive function reports the $2$-partition and
returns if $i=n$. Otherwise, it checks whether the next interval in
$\mathcal{J}_{4}$ can be added to either part without forming a star
$K_{1,3}$, then recurses on the resulting at most two good partial
$2$-partitions of the first $i+1$ intervals.

We wrote a C program implementing this simple branch-and-bound algorithm; see
the source code in the appendix. On a typical laptop computer, it took less
than two minutes for the program to verify that $\mathcal{J}_{4}$ admits no
good $2$-partition. ∎

Recall (1) earlier. By Lemma 5, Lemma 6, and Lemma 7, we have
$\check{\kappa}(4,2)=\check{\kappa}(5,2)=\check{\kappa}(6,2)=3$. The previous
three lemmas also imply that interval graphs admitting no vertex partition
into less than three proper interval graphs do not always contain $H_{3}$
(which has claw number $9$) as an induced subgraph. This partially answers an
open question of Gardi [9, page 53] in the negative.

The following lemma shows that $\check{\kappa}(3,2)\leq 2$, and hence
$\check{\kappa}(3,2)=2$.

######  Lemma 8.

Any interval graph with claw number at most $3$ admits a vertex partition into
two subgraphs with claw number at most $2$.

###### Proof.

Let $G$ be an interval graph, and let $\mathcal{I}$ be an interval
representation of $G$ with integer endpoints. Let $j=\vartheta(G)$. Run the
sweepline algorithm to obtain an independent set of $j$ intervals $T_{i}$ in
$\mathcal{I}$, and a vertex partition of $\mathcal{I}$ into $j$ cliques
$\mathcal{I}^{\prime}_{i}$, where $T_{i}\in\mathcal{I}^{\prime}_{i}$ for
$1\leq i\leq j$. For $h\in\\{0,1,2,3\\}$, let $\mathcal{J}_{h}$ be the union
of the subfamilies $\mathcal{I}^{\prime}_{i}$ with $i\bmod 4=h$. We next show
that the subgraph of $G$ induced by $\mathcal{J}_{0}\cup\mathcal{J}_{1}$ has
claw number at most $2$. The argument for $\mathcal{J}_{2}\cup\mathcal{J}_{3}$
is similar.

Suppose for contradiction that $\mathcal{J}_{0}\cup\mathcal{J}_{1}$ contains
four intervals $O,A,B,C$ representing a star $K_{1,3}$, where $O$ is the
center, and $A,B,C$ are the three leaves. Suppose that
$O\in\mathcal{I}^{\prime}_{o}$, $A\in\mathcal{I}^{\prime}_{a}$,
$B\in\mathcal{I}^{\prime}_{b}$, and $C\in\mathcal{I}^{\prime}_{c}$, where
$a<b<c$. Note there are only two different values $0$ and $1$ for $o,a,b,c$
modulo $4$. We claim that if $a>o-3$, then $c\geq o+3$. Consider two cases. If
$o\bmod 4=0$, then the condition $a>o-3$ implies that $a\geq o$, and hence
$b\geq o+1$, and hence $c\geq o+4$. If $o\bmod 4=1$, then the condition
$a>o-3$ implies that $a\geq o-1$, and hence $b\geq o$, and hence $c\geq o+3$.

In summary, we must have either $a\leq o-3$ or $c\geq o+3$:

  * •

If $a\leq o-3$, then the $o-a$ intervals $T_{i}$ for $a\leq i\leq o-1$ and the
interval $O$ would together be $o-a+1\geq 4$ pairwise-disjoint intervals
intersecting $A$.

  * •

If $c\geq o+3$, then the $c-o$ intervals $T_{i}$ for $o\leq i\leq c-1$ and the
interval $C$ would together be $c-o+1\geq 4$ pairwise-disjoint intervals
intersecting $O$.

In both cases, we reach a contradiction to our assumption that $G$ has claw
number at most $3$. ∎

We finally prove that $\check{\kappa}(5,3)=2$. The lower bound of
$\check{\kappa}(5,3)\geq 2$ is obvious. The following lemma gives the tight
upper bound of $\check{\kappa}(5,3)\leq 2$:

######  Lemma 9.

Any interval graph with claw number at most $5$ admits a vertex partition into
two subgraphs with claw number at most $3$.

###### Proof.

Let $G$ be an interval graph with claw number at most $5$, and let
$\mathcal{I}$ be an interval representation of $G$. Partition $\mathcal{I}$
into two subfamilies $\mathcal{I}_{<2}$ and $\mathcal{I}_{\geq 2}$ of
intervals properly containing less than two and at least two, respectively,
disjoint intervals in $\mathcal{I}$. Since any interval that intersects more
than three disjoint intervals must properly contain at least two of them, the
subgraph of $G$ induced by intervals in $\mathcal{I}_{<2}$ clearly has claw
number at most $3$. We claim that the subgraph of $G$ induced by intervals in
$\mathcal{I}_{\geq 2}$ has claw number at most $3$ too.

Suppose the contrary. Let $C$ and $L_{1},L_{2},L_{3},L_{4}$ be intervals in
$\mathcal{I}_{\geq 2}$ representing the center and the four leaves of a star
$K_{1,4}$, where $L_{1},L_{2},L_{3},L_{4}$ are disjoint and ordered from left
to right. Then $C$ properly contains $L_{2}$ and $L_{3}$. Since each of
$L_{2}$ and $L_{3}$ also properly contains at least two disjoint intervals in
$\mathcal{I}$, $C$ intersects at least six disjoint intervals in
$\mathcal{I}$, contradicting our assumption that $G$ has claw number at most
$5$. ∎

The proof of Theorem 3 is now complete.

##  6 Approximation algorithm

In this section we prove Theorem 4.

Albertson et al. [3, Theorem 4] showed that $\check{\kappa}(w,1)\leq w$ for
any $w\geq 1$, which implies that
$\check{\kappa}(v+2,v)=\check{\kappa}(3,1)\leq 3$ when $v=1$. When $v=2$, by
our upper bound of $\check{\kappa}(w,v)\leq\lfloor\log_{v+1}3(w-1)/2\rfloor+2$
for $w>v=2$ in Corollary 2, we have
$\check{\kappa}(v+2,v)=\check{\kappa}(4,2)\leq\lfloor\log_{3}9/2\rfloor+2=3$.
When $v=3$, we have $\check{\kappa}(v+2,v)=\check{\kappa}(5,3)\leq 2$ by Lemma
9. When $v>3$, we have
$\check{\kappa}(v+2,v)\leq\lfloor\log_{v+1}(v+1)/(v-2)\rfloor+2=2$ by
Corollary 2. In summary, we have $\check{\kappa}(v+2,v)\leq 3$ when $1\leq
v\leq 2$, and $\check{\kappa}(v+2,v)\leq 2$ when $v\geq 3$. Since the proof of
Albertson et al. [3, Theorem 4] and our proofs of these upper bounds are
constructive, we have the following proposition:

######  Proposition 1.

For any $v\geq 1$, there is a polynomial-time algorithm that partitions any
interval graph with claw number at most $v+2$ into $t$ induced subgraphs with
claw number at most $v$, with $t=3$ for $1\leq v\leq 2$, and $t=2$ for $v\geq
3$.

Our approximation algorithm for Min-Partition$(v)$ works as follows. Given an
interval graph $G$, first obtain an interval representation $\mathcal{I}$ of
$G$. Initialize $\mathcal{J}\leftarrow\mathcal{I}$ and $i\leftarrow 1$. While
$\mathcal{J}$ is not empty, let $\mathcal{J}^{\prime}$ be the subfamily of
intervals in $\mathcal{J}$ each properly containing at least $v+1$ disjoint
intervals in $\mathcal{J}$, let
$\mathcal{I}_{i}\leftarrow\mathcal{J}\setminus\mathcal{J}^{\prime}$, then
update $\mathcal{J}\leftarrow\mathcal{J}^{\prime}$ and $i\leftarrow i+1$.

Let $k$ be the maximum round $i$ in which $\mathcal{J}$ is not empty. Then
$(\mathcal{I}_{1},\ldots,\mathcal{I}_{k})$ is a $k$-partition of
$\mathcal{I}$. For $1\leq i\leq k$, since each interval in $\mathcal{I}_{i}$
properly contains at most $v$ disjoint intervals in $\mathcal{I}_{i}$, the
subgraph of $G$ induced by each subfamily $\mathcal{I}_{i}$ has claw number at
most $v+2$. Apply the algorithm in Proposition 1 to partition the subgraph of
$G$ induced by each subfamily $\mathcal{I}_{i}$ into $t$ subgraphs, with $t=3$
for $1\leq v\leq 2$, and $t=2$ for $v\geq 3$. Then $G$ is partitioned into
$kt$ subgraphs with claw number at most $v$.

Observe that for $2\leq i\leq k$, each interval in $\mathcal{I}_{i}$ properly
contains at least $v+1$ disjoint intervals in $\mathcal{I}_{i-1}$. Thus $G$
contains $A_{k,v}$ as an induced subgraph, and it follows by Lemma 2 that $G$
admits no vertex partition into less than $k$ induced subgraphs with claw
number at most $v$. Thus our algorithm for Min-Partition$(v)$ achieves an
approximation ratio of $t$, with $t=3$ for $1\leq v\leq 2$, and $t=2$ for
$v\geq 3$. This completes the proof of Theorem 4.

##  7 Open questions

For $k\geq 2$ and $v\geq 2$, is there a polynomial-time algorithm for
$k$-Partition$(v)$ in interval graphs? In particular, for $k=v=2$, is there a
polynomial-time algorithm that decides whether an interval graph admits a
vertex partition into two proper interval graphs? Can the gaps between lower
and upper bounds in Theorem 2 and Corollary 2 be reduced?

## References

  * [1] D. Achlioptas. The complexity of $G$-free colourability. _Discrete Mathematics_ , 165/166:21–30, 1997.
  * [2] A. Adiga and L. S. Chandran. Cubicity of interval graphs and the claw number. _Journal of Graph Theory_ , 65:323–333, 2010.
  * [3] M. O. Albertson, R. E. Jamison, S. T. Hedetniemi, and S. C. Locke. The subchromatic number of a graph. _Discrete Mathematics_ , 74:33–49, 1989.
  * [4] K. P. Bogart and D. B. West. A short proof that ‘proper = unit’. _Discrete Mathematics_ , 201:21–23, 1999.
  * [5] H. Broersma, F. V. Fomin, J. Nešetřil, and G. J. Woeginger. More about subcolorings. _Computing_ , 69:187-203, 2002.
  * [6] A. Farrugia. Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. _The Electronic Journal of Combinatorics_ , 11:#R46, 2004.
  * [7] P. C. Fishburn. _Interval Orders and Interval Graphs: A Study of Partially Ordered Sets_. John Wiley & Sons, 1985.
  * [8] R. Gandhi, B. Greening Jr., S. Pemmaraju, and R. Raman. Sub-coloring and hypo-coloring interval graphs. _Discrete Mathematics, Algorithms and Applications_ , 02:#331, 2010.
  * [9] F. Gardi. On partitioning interval graphs into proper interval subgraphs and related problems. _Journal of Graph Theory_ , 68:38–54, 2011.
  * [10] M. C. Golumbic. _Algorithmic Graph Theory and Perfect Graphs_ , Second Edition. Elsevier, 2004.

### A counterexample

Gardi reported [9, Lemma 2.3] that for $t>1$, any $K_{1,t}$-free interval
graph admits a vertex partition into
$\big{\lceil}\log_{3}\frac{3t-3}{2}\big{\rceil}$ proper interval graphs. By
substituting $t$ with $w+1$, this would imply that
$\check{\kappa}(w,2)\leq\lceil\log_{3}3w/2\rceil$ for $w\geq 1$, in
particular, $\check{\kappa}(w,2)\leq 2$ for $w\leq 6$. But this cannot hold,
since we proved in Theorem 3 that
$\check{\kappa}(4,2)=\check{\kappa}(5,2)=\check{\kappa}(6,2)=3$; see our
Lemmas 5, 6, and 7. We refer to Figure 7 for a counterexample that identifies
a flaw in the proof of [9, Lemma 2.3]. This flaw also affects several other
results, including an upper bound on $\kappa(n,2)$ [9, Proposition 2.7].

Figure 7: A counterexample to the correctness of the algorithm Color-Cliques-
Logarithmic in Gardi’s constructive proof of [9, Lemma 2.3] with $t=6$. The
nine intervals are first partitioned into seven cliques $C_{0}=\\{1,2\\}$,
$C_{1}=\\{3\\}$, $C_{2}=\\{4\\}$, $C_{3}=\\{5,6\\}$ $C_{4}=\\{7\\}$,
$C_{5}=\\{8\\}$, $C_{6}=\\{9\\}$ by the algorithm Canonical-Partition-Into-
Cliques, and then grouped into two parts $\mathcal{C}_{0}=\\{3,4,7,8\\}$ and
$\mathcal{C}_{1}=\\{1,2,5,6,9\\}$ by the algorithm Color-Cliques-Logarithmic.
The subgraph represented by $\mathcal{C}_{1}$ contains an induced star
$K_{1,3}$ with center $5$ and three leaves $1,6,9$, and hence is not a proper
interval graph as claimed.

## Source code for Lemma 7

⬇

#include <stdio.h>

#define N 105

#define K 512

int ll[N], rr[N], xx[N][K], yy[N][K], zz[N][K], kk[N];

char part[N];

int min(int a, int b) { return a < b ? a : b; }

int max(int a, int b) { return a > b ? a : b; }

int a(int i, int j) { return max(ll[i], ll[j]) < min(rr[i], rr[j]); }

int claw(int i, int j, int k, int l) {

return a(i, j) && a(i, k) && a(i, l) && !a(j, k) && !a(j, l) && !a(k, l);

}

int bad(int i, int j, int k, int l) {

return claw(i, j, k, l) || claw(j, k, l, i) || claw(k, l, i, j) || claw(l, i,
j, k);

}

int good(int i) {

int h, p = part[i];

for (h = 0; h < kk[i]; h++)

if (part[xx[i][h]] == p && part[yy[i][h]] == p && part[zz[i][h]] == p)

return 0;

return 1;

}

int solve(int i) {

if (i == N) {

printf("good\n");

return 1;

}

for (part[i] = 0; part[i] <= 1; part[i]++)

if (good(i) && solve(i + 1))

return 1;

return 0;

}

int main() {

int n, l, r, i;

n = 0;

for (r = 2; r <= 21; r++)

for (l = r - 2; l >= 0 && l >= r - 7; l\--)

ll[n] = l, rr[n] = r, n++;

printf("n = %d\n", n);

for (i = 0; i < n; i++) {

int x, y, z, k = 0;

for (x = 0; x < i; x++)

for (y = x + 1; y < i; y++)

for (z = y + 1; z < i; z++)

if (bad(i, x, y, z)) {

if (k == K) {

printf("K is too small\n");

return 0;

}

xx[i][k] = x, yy[i][k] = y, zz[i][k] = z, k++;

}

kk[i] = k;

}

if (!solve(1))

printf("no good\n");

return 0;

}