Track number of line graphs

DOI10.4310/JOC.2018.V9.N4.A10zbMATH Open1401.05194arXiv1612.08347WikidataQ128832160 ScholiaQ128832160MaRDI QIDQ1630705FDOQ1630705

Authors: Deepak Rajendraprasad 

Publication date: 10 December 2018

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

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.

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

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

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)

Cited In (1)

• Title not available (Why is that?)

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)