Contents Online

# Journal of Combinatorics

## Volume 9 (2018)

### Number 4

### Track number of line graphs

Pages: 747 – 754

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n4.a10

#### Author

#### 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 $\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

Received 26 December 2016

Published 7 December 2018