Graphs of small dimensions

DOI10.1007/BF01300127MaRDI QIDQ1912752zbMATH OpenOpenAlexFDO

Authors Nancy Eaton, Vojtěch Rödl

Publication date 14 May 1996

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01300127

zbMATH Keywords

product dimensionset intersection representation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Relations of low-dimensional topology with graph theory (57M15)

Review text

An upper bound is given to the direct product dimension of any graph of fixed order and fixed maximum degree. Bounds are also given to the minimum size of a set intersection representation of a graph.

Recommendations

• scientific article; zbMATH DE number 3970801
• The dimension of sums of graphs
• The dimension of graphs with respect to the direct powers of a two-element graph
• On set intersection representations of graphs
• Intersection dimension and graph invariants

Cites work

• A simple proof of the Galvin-Ramsey property of the class of all finite graphs and a dimension of a graph
• Covering graphs by the minimum number of equivalence relations
• On a product dimension of graphs
• On the dimensions of ordered sets of bounded degree
• Orthogonal partitions and covering of graphs
• Probability Inequalities for Sums of Bounded Random Variables
• The Representation of a Graph by Set Intersections

Cited in

(23)

• Graphs with small book thickness
• On dimensional properties of graphs
• Kneser ranks of random graphs and minimum difference representations
• Constant tolerance intersection graphs of subtrees of a tree
• Compact graphings
• Intersection dimension and graph invariants
• On induced and isometric embeddings of graphs into the strong product of paths
• Intersection dimension and maximum degree
• Characterizing Graphs of Small Carving-Width
• On a product dimension of bipartite graphs
• Thin strip graphs
• On economical set representations of graphs
• On set intersection representations of graphs
• scientific article; zbMATH DE number 3970801 (Why is no real title available?)
• The dimension of graphs with respect to the direct powers of a two-element graph
• Product dimension of forests and bounded treewidth graphs
• Kneser ranks of random graphs and minimum difference representations
• Graph Stories in Small Area
• The dimension of sums of graphs
• The dimension of sums of graphs
• Some results and problems on clique coverings of hypergraphs
• On set representation of bounded degree hypergaphs
• Bounded-depth succinct encodings and the structure they imply on graphs

This page was built for publication: Graphs of small dimensions

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