Intersection dimensions of graph classes

DOI10.1007/BF02986660MaRDI QIDQ1334942zbMATH OpenOpenAlexFDO

Authors Jan Kratochvíl, Zsolt Tuza

Publication date 26 September 1994

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

intersection dimensionintersection graphpermutation graphsplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Generalized Ramsey theory (05C55) Graph theory (05C99)

Review text

``The intersection dimension of a graph \(G\) with respect to a class \(A\) of graphs is the minimum \(k\) such that \(G\) is the intersection of at most \(k\) graphs on vertex set \(V(G)\) each of which belongs to \(A\). We consider the question when the intersection dimension of a certain family of graphs is bounded or unbounded. If \(A\) is hereditary and does not contain all graphs, then the intersection dimension of all graphs with respect to \(A\) is unbounded. The intersection dimension of planar graphs with respect to permutation graphs is bounded.

Recommendations

• Intersection dimension and graph invariants
• Intersection dimension and maximum degree
• scientific article; zbMATH DE number 811560
• Intersection dimension of bipartite graphs
• Characterizing intersection classes of graphs

Cites work

• A characterization of Robert's inequality for boxicity
• A note on circular dimension
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Grid intersection graphs and boxicity
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3508545 (Why is no real title available?)
• Interval representations of planar graphs
• On dimensional properties of graphs
• On grid intersection graphs
• Partitionstheoreme für Graphen
• The circular dimension of a graph

Cited in

(18)

• An upper bound for cubicity in terms of boxicity
• Characterizing intersection classes of graphs
• Representing graphs as the intersection of cographs and threshold graphs
• Intersection dimension and graph invariants
• Intersection dimension and maximum degree
• scientific article; zbMATH DE number 5149077 (Why is no real title available?)
• Ferrers dimension of grid intersection graphs
• Intersection dimension of bipartite graphs
• Refining the hierarchies of classes of geometric intersection graphs
• Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates
• Intersection of chordal graphs and some related partition problems
• A survey on the boxicity and cubicity of graphs
• Graphs of bounded chordality
• On generalizations of pairwise compatibility graphs
• Some bounds on the threshold dimension of graphs
• Grid intersection graphs and order dimension
• Boxicity of zero divisor graphs
• Forbidden induced subgraphs for bounded p-intersection number

This page was built for publication: Intersection dimensions of graph classes

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