Track number of line graphs

DOI10.4310/JOC.2018.V9.N4.A10MaRDI QIDQ1630705zbMATH OpenWikidataFDO

Authors Deepak Rajendraprasad

Publication date 10 December 2018

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.08347

zbMATH Keywords

interval graphsRamsey theoryline graphstrack number

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76) Ramsey theory (05D10)

Abstract: The track number $au(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 $lglgchi(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 $au(L(K_n))$ of the line graph of the complete graphs $K_n$ is at least $lglgn-o(1)$. This is asymptotically tight and it improves the bound of $Omega(lglgn/lglglgn)$ in MSW15. Next we show that for a family of graphs $mathcalG$, $au(L(G)):GinmathcalG$ is bounded if and only if $chi(G):GinmathcalG$ 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.

Recommendations

• Ordered Ramsey theory and track representations of graphs
• Improved bounds for track numbers of planar graphs
• scientific article; zbMATH DE number 1185295
• scientific article; zbMATH DE number 2159655
• On interval representations of graphs

Cited in

(1)

• scientific article; zbMATH DE number 1185295 (Why is no real title available?)

This page was built for publication: Track number of line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1630705)