A note on intersection dimensions of graph classes

Petr Hliněný; Aleš Kuběna

Commentationes Mathematicae Universitatis Carolinae (1995)

  • Volume: 36, Issue: 2, page 255-261
  • ISSN: 0010-2628

Abstract

top
The intersection dimension of a graph G with respect to a class 𝒜 of graphs is the minimum k such that G is the intersection of some k graphs on the vertex set V ( G ) belonging to 𝒜 . In this paper we follow [ Kratochv’ıl J., Tuza Z.: Intersection dimensions of graph classes, Graphs and Combinatorics 10 (1994), 159–168 ] and show that for some pairs of graph classes 𝒜 , ℬ the intersection dimension of graphs from ℬ with respect to 𝒜 is unbounded.

How to cite

top

Hliněný, Petr, and Kuběna, Aleš. "A note on intersection dimensions of graph classes." Commentationes Mathematicae Universitatis Carolinae 36.2 (1995): 255-261. <http://eudml.org/doc/247769>.

@article{Hliněný1995,
abstract = {The intersection dimension of a graph $G$ with respect to a class $\mathcal \{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 $\mathcal \{A\}$. In this paper we follow [ Kratochv’ıl J., Tuza Z.: Intersection dimensions of graph classes, Graphs and Combinatorics 10 (1994), 159–168 ] and show that for some pairs of graph classes $\mathcal \{A\}$, $\mathcal \{B\}$ the intersection dimension of graphs from $\mathcal \{B\}$ with respect to $\mathcal \{A\}$ is unbounded.},
author = {Hliněný, Petr, Kuběna, Aleš},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {intersection graph; intersection dimension; intersection graph; graph classes; intersection dimension},
language = {eng},
number = {2},
pages = {255-261},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {A note on intersection dimensions of graph classes},
url = {http://eudml.org/doc/247769},
volume = {36},
year = {1995},
}

TY - JOUR
AU - Hliněný, Petr
AU - Kuběna, Aleš
TI - A note on intersection dimensions of graph classes
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1995
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 36
IS - 2
SP - 255
EP - 261
AB - The intersection dimension of a graph $G$ with respect to a class $\mathcal {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 $\mathcal {A}$. In this paper we follow [ Kratochv’ıl J., Tuza Z.: Intersection dimensions of graph classes, Graphs and Combinatorics 10 (1994), 159–168 ] and show that for some pairs of graph classes $\mathcal {A}$, $\mathcal {B}$ the intersection dimension of graphs from $\mathcal {B}$ with respect to $\mathcal {A}$ is unbounded.
LA - eng
KW - intersection graph; intersection dimension; intersection graph; graph classes; intersection dimension
UR - http://eudml.org/doc/247769
ER -

References

top
  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. (1983) Zbl0524.05059MR0712922
  2. Cozzens M.B., Roberts F.S., On dimensional properties of graphs, Graphs and Combinatorics 5 (1989), 29-46. (1989) Zbl0675.05054MR0981229
  3. Feinberg R.B., The circular dimension of a graph, Discrete Math. 25 (1979), 27-31. (1979) Zbl0392.05057MR0522744
  4. Golumbic M.C., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980. Zbl1050.05002MR0562306
  5. Goodman J.E., Pollack R., Upper bounds for configurations and polytopes in R d , Discrete Computational Geometry 1 (1986), 219-227. (1986) MR0861891
  6. Janson S., Kratochvíl J., Thresholds for classes of intersection graphs, Discrete Math. 108 (1992), 307-326. (1992) MR1189853
  7. Kratochvíl J., Matoušek J., Intersection graphs of segments, J. Combin. Theory Ser. B 62 (1994), 289-315. (1994) MR1305055
  8. Kratochvíl J., Tuza Z., Intersection dimensions of graph classes, Graphs and Combinatorics 10 (1994), 159-168. (1994) MR1289974

NotesEmbed ?

top

You must be logged in to post comments.