On the Boxicity of Kneser Graphs and Complements of Line Graphs

DOI10.1016/J.DISC.2023.113333MaRDI QIDQ6366966arXivFDO

Authors Marco Caoduro, Lyuben Lichev

Publication date 6 May 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2023.113333

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

arXiv classification

math.CO

Abstract: An axis-parallel $d$-dimensional box is a cartesian product $I_{1}imes{I}_{2}imesdotsimes{I}_b$ where $I_i$ is a closed sub-interval of the real line. For a graph $G=(V,E)$, the $boxicityofG$, denoted by $extbox(G)$, is the minimum dimension $d$ such that $G$ is the intersection graph of a family $(B_v{)}_{vinV}$ of $d$-dimensional boxes in $mathbb{R}^d$. Let $k$ and $n$ be two positive integers such that $ngeq2k+1$. The $Knesergraph$ $Kn(k,n)$ is the graph with vertex set given by all subsets of $1,2,dots,n$ of size $k$ where two vertices are adjacent if their corresponding $k$-sets are disjoint. In this note, we derive a general upper bound for $extbox(Kn(k,n))$, and a lower bound in the case $nge2k^3-2k^2+1$, which matches the upper bound up to an additive factor of $Theta(k^2)$. Our second contribution is to provide upper and lower bounds for the boxicity of the complement of the line graph of any graph $G$, and as a corollary, we derive that $extbox(Kn(2,n))inn-3,n-2$ for every $nge5$.

This page was built for publication: On the Boxicity of Kneser Graphs and Complements of Line Graphs

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