Product dimension of forests and bounded treewidth graphs (Q396879)

Summary: The product dimension of a graph \(G\) is defined as the minimum natural number \(l\) such that \(G\) is an induced subgraph of a direct product of \(l\) complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and \(k\)-degenerate graphs. We show that every forest on \(n\) vertices has product dimension at most \(1.441 \log n + 3\). This improves the best known upper bound of \(3 \log n\) for the same due to \textit{S. Poljak} and \textit{A. Pultr} [Discrete Math. 34, 165--171 (1981; Zbl 0476.05075)]. The technique used in arriving at the above bound is extended and combined with a well-known result on the existence of orthogonal Latin squares to show that every graph on \(n\) vertices with treewidth at most \(t\) has product dimension at most \((t+2)(\log n + 1)\). We also show that every \(k\)-degenerate graph on \(n\) vertices has product dimension at most \(\lceil 5.545 k \log n \rceil + 1\). This improves the upper bound of \(32 k \log n\) for the same by \textit{N. Eaton} and \textit{V. Rödl} [Combinatorica 16, No. 1, 59--85 (1996; Zbl 0853.05049)].