Product dimension of forests and bounded treewidth graphs

MaRDI QIDQ396879zbMATH OpenFDO

Authors L. Sunil Chandran, Rogers Mathew, Deepak Rajendraprasad, Roohani Sharma

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.2218, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p42

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

forestorthogonal Latin squaresbounded treewidth graphrepresentation numberk-degenerate graphproduct dimension

Mathematics Subject Classification ID

Trees (05C05) Graph representations (geometric and intersection representations, etc.) (05C62)

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 a product dimension at most 1.441logn+3. This improves the best known upper bound of 3logn for the same due to Poljak and Pultr. The technique used in arriving at the above bound is extended and combined with a result on existence of orthogonal Latin squares to show that every graph on n vertices with a treewidth at most t has a product dimension at most (t+2)(logn+1). We also show that every k-degenerate graph on n vertices has a product dimension at most ceil{8.317klogn}+1. This improves the upper bound of 32klogn for the same by Eaton and Rodl.

Recommendations

• scientific article; zbMATH DE number 3970801
• Maximum induced forests in graphs of bounded treewidth
• Maximum induced forests of product graphs
• The dimension of sums of graphs
• Tree-width of product of a connected graph and a \(k\)-connected partial \(k\)-tree

Cites work

• scientific article; zbMATH DE number 4047780 (Why is no real title available?)
• A managed Bayesian risk approach for decision making alternatives
• A simple proof of the Galvin-Ramsey property of the class of all finite graphs and a dimension of a graph
• Boxicity and treewidth
• Covering graphs by the minimum number of equivalence relations
• Further Results on the Construction of Mutually Orthogonal Latin Squares and the Falsity of Euler's Conjecture
• Graphs of small dimensions
• On a product dimension of graphs
• On the dimension of trees
• Representations of disjoint unions of complete graphs
• Representations of graphs and orthogonal latin square graphs
• Representations of graphs modulo \(n\)

Cited in

(2)

• Lower bounds for treewidth of product graphs
• Induced embeddings into Hamming graphs

This page was built for publication: Product dimension of forests and bounded treewidth graphs

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