Track number of line graphs

Abstract

The track number $\tau (G)$ of a graph $G$ is the minimum number of interval graphs whose union is $G$. We show that the track number of the line graph $L(G)$ of a triangle-free graph $G$ is at least $\lg \lg \chi (G)+1$, where $\chi (G)$ is the chromatic number of $G$. Using this lower bound and two classical Ramsey-theoretic results from literature, we answer two questions posed by Milans, Stolee, and West [J. Combinatorics, 2015] (MSW15). First we show that the track number $\tau (L(K_n))$ of the line graph of the complete graphs $K_n$ is at least $\lg \lg n-o(1)$. This is asymptotically tight and it improves the bound of $\Omega (\lg \lg n/\lg \lg \lg n)$ in MSW15. Next we show that for a family of graphs $\mathcal{G}$, $\{\tau (L(G)):G\in \mathcal{G}\}$ is bounded if and only if $\{\chi (G):G\in \mathcal{G}\}$ is bounded. This affirms a conjecture in MSW15. All our lower bounds apply even if one enlarges the covering family from the family of interval graphs to the family of chordal graphs.