| Title:
|
A note on intersection dimensions of graph classes (English) |
| Author:
|
Hliněný, Petr |
| Author:
|
Kuběna, Aleš |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
36 |
| Issue:
|
2 |
| Year:
|
1995 |
| Pages:
|
255-261 |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
intersection graph |
| Keyword:
|
intersection dimension |
| MSC:
|
05C10 |
| MSC:
|
05C30 |
| MSC:
|
05C70 |
| MSC:
|
05C75 |
| idZBL:
|
Zbl 0838.05042 |
| idMR:
|
MR1357527 |
| . |
| Date available:
|
2009-01-08T18:17:44Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118754 |
| . |
| Reference:
|
[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. Zbl 0524.05059, MR 0712922 |
| Reference:
|
[2] Cozzens M.B., Roberts F.S.: On dimensional properties of graphs.Graphs and Combinatorics 5 (1989), 29-46. Zbl 0675.05054, MR 0981229 |
| Reference:
|
[3] Feinberg R.B.: The circular dimension of a graph.Discrete Math. 25 (1979), 27-31. Zbl 0392.05057, MR 0522744 |
| Reference:
|
[4] Golumbic M.C.: Algorithmic Graph Theory and Perfect Graphs.Academic Press, New York, 1980. Zbl 1050.05002, MR 0562306 |
| Reference:
|
[5] Goodman J.E., Pollack R.: Upper bounds for configurations and polytopes in $R^d$.Discrete Computational Geometry 1 (1986), 219-227. MR 0861891 |
| Reference:
|
[6] Janson S., Kratochvíl J.: Thresholds for classes of intersection graphs.Discrete Math. 108 (1992), 307-326. MR 1189853 |
| Reference:
|
[7] Kratochvíl J., Matoušek J.: Intersection graphs of segments.J. Combin. Theory Ser. B 62 (1994), 289-315. MR 1305055 |
| Reference:
|
[8] Kratochvíl J., Tuza Z.: Intersection dimensions of graph classes.Graphs and Combinatorics 10 (1994), 159-168. MR 1289974 |
| . |
