Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
intersection graph; intersection dimension
intersection graph; intersection dimension
Summary:
The intersection dimension of a graph $G$ with respect to a class $\Cal A$ of graphs is the minimum $k$ such that $G$ is the intersection of some $k$ graphs on the vertex set $V(G)$ belonging to $\Cal A$. In this paper we follow [\,Kratochv'\i l J., Tuza Z.: {\sl Intersection dimensions of graph classes\/}, Graphs and Combinatorics 10 (1994), 159--168\,] and show that for some pairs of graph classes $\Cal A$, $\Cal B$ the intersection dimension of graphs from $\Cal B$ with respect to $\Cal A$ is unbounded.
References:
[1] Cozzens M.B., Roberts F.S.: Computing the boxicity of a graph by covering its complement by cointerval graphs. Discrete Appl. Math. 6 (1983), 217-228. MR 0712922 | Zbl 0524.05059
[2] Cozzens M.B., Roberts F.S.: On dimensional properties of graphs. Graphs and Combinatorics 5 (1989), 29-46. MR 0981229 | Zbl 0675.05054
[3] Feinberg R.B.: The circular dimension of a graph. Discrete Math. 25 (1979), 27-31. MR 0522744 | Zbl 0392.05057
[4] Golumbic M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980. MR 0562306 | Zbl 1050.05002
[5] Goodman J.E., Pollack R.: Upper bounds for configurations and polytopes in $R^d$. Discrete Computational Geometry 1 (1986), 219-227. MR 0861891
[6] Janson S., Kratochvíl J.: Thresholds for classes of intersection graphs. Discrete Math. 108 (1992), 307-326. MR 1189853
[7] Kratochvíl J., Matoušek J.: Intersection graphs of segments. J. Combin. Theory Ser. B 62 (1994), 289-315. MR 1305055
[8] Kratochvíl J., Tuza Z.: Intersection dimensions of graph classes. Graphs and Combinatorics 10 (1994), 159-168. MR 1289974
Search
Partner of
