# Partitioning an interval graph into matchings

Consider $C$, a family of intervals on $R$, such that each $p ∈ R$ is contained in at most $m$ of these intervals. Prove that there is a partition of $C$ into $m$ classes $C_1, ..., C_m$ so that each $C_i$ consists of pairwise disjoint intervals.

My idea is to represent the family of intervals as a bipartite graph, $B$. Then, the problem just becomes finding a partition of the edge set of $B$ into $m$ disjoint matchings, which by König's theorem is equivalent to showing that the maximum degree of a vertex in $B$ is $m$. However, I am at a loss on how to represent this interval graph as a bipartite graph.

NOTE: I'm looking for a graph theoretic way to solve this!

-

I don't know why you want to use bipartite graphs here. This problem is easily solved with direct greedy approach and induction. Just split $C$ into $C_1$ and $C'$ such that for each $p \in \mathbb{R}$ there is at most $m-1$ intervals $C'$ that contain $p$. Repeat until done.
To give you some hint: Let $[l_1,r_1] \in C_1$, then pick an interval $[l_2,r_2] \in C$ such that its smaller end is the closest possible to $r_1$, that is, $l_2 = \min \{ l \mid [l,r] \in C, r_1 < l\}$. We know that at $r_1$ there are at most $m$ intervals, so for $p \in (r_1,l_2)$ we have at most $m-1$ intervals (note that in-between $(r_1,l_2)$ no new interval could have started because $l_2$ is minimal).