Product dimension of forests and bounded treewidth graphs

L. Sunil Chandran¹ ; Rogers Mathew² ; Deepak Rajendraprasad¹ ; Roohani Sharma¹

¹Indian Institute of Science, Bangalore, India
²Dalhousie University, Halifax, Canada

The electronic journal of combinatorics, Tome 20 (2013) no. 3

Résumé

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 Poljak and Pultr. 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 Eaton and Rődl.

Détail

DOI : 10.37236/2698

Classification : 05C05, 05C62
Mots-clés : product dimension, representation number, forest, bounded treewidth graph, k-degenerate graph, orthogonal Latin squares