Product dimension of forests and bounded treewidth graphs

zbMATH Open1295.05077arXiv1209.2218MaRDI QIDQ396879FDOQ396879

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)

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.

Full work available at URL: https://arxiv.org/abs/1209.2218

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

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

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)

Cites Work

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

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)