Track number of line graphs

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 $\mathrm{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 $\mathrm{lg \: lg \:} n-o(1)$. This is asymptotically tight and it improves the bound of $\Omega (\mathrm{lg \: lg \:} n \: / \: \mathrm{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.

Keywords

track number, line graphs, interval graphs, Ramsey theory

2010 Mathematics Subject Classification

05C15, 05C20, 05C55, 05C62

Full Text (PDF format)

Received 26 December 2016

Published 7 December 2018