Header menu link for other important links
X
Product dimension of forests and bounded treewidth graphs
L. Sunil Chandran, R. Mathew, , R. Sharma
Published in
2013
Volume: 20
   
Issue: 3
Abstract
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 ⌈5.545k log n⌉+1. This improves the upper bound of 32k log n for the same by Eaton and Rödl.
About the journal
JournalElectronic Journal of Combinatorics
ISSN10778926