Track number of line graphs

The track number $τ(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 χ(G) + 1$, where $χ(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 $τ(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 $Ω(\lg\lg n/ \lg\lg\lg n)$ in MSW15. Next we show that for a family of graphs $\mathcal{G}$, $\{τ(L(G)):G \in \mathcal{G}\}$ is bounded if and only if $\{χ(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.

No reviews yet.

No comments yet.