| Title:
|
$k$-Ramsey classes and dimensions of graphs (English) |
| Author:
|
Kratochvíl, Jan |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
36 |
| Issue:
|
2 |
| Year:
|
1995 |
| Pages:
|
263-268 |
| . |
| Category:
|
math |
| . |
| Summary:
|
In this note, we introduce the notion of $k$-Ramsey classes of graphs and we reveal connections to intersection dimensions of graphs. (English) |
| Keyword:
|
graph |
| Keyword:
|
intersection graph |
| Keyword:
|
intersection dimension |
| Keyword:
|
Ramsey property |
| MSC:
|
05C55 |
| MSC:
|
05C99 |
| MSC:
|
05D10 |
| idZBL:
|
Zbl 0842.05063 |
| idMR:
|
MR1357528 |
| . |
| Date available:
|
2009-01-08T18:17:48Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118755 |
| . |
| Reference:
|
[1] Cozzens M.B., Roberts F.S.: On dimensional properties of graphs.Graphs and Combinatorics 5 (1989), 29-46. Zbl 0675.05054, MR 0981229 |
| Reference:
|
[2] Deuber W.: Partitionstheoreme für Graphen.Comment. Math. Helvetica 50 (1975), 311-320. Zbl 0313.05120, MR 0401546 |
| 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] Hliněný P., Kuběna A.: A note on intersection dimensions of graph classes.Commentationes Math. Univ. Carolinae 36 (1995). MR 1357527 |
| Reference:
|
[6] Jansen S., Kratochvíl J.: Thresholds for classes of intersection graphs.Discrete Math. 108 (1992), 307-326. MR 1189853 |
| Reference:
|
[7] Koebe M.: On a new class of intersection graphs.in: Graphs and Complexity (M. Fiedler and J. Nešetřil, eds.), Annals of Discrete Math. 51, North Holland, Amsterdam, 1992 (Proceedings 4th Czechoslovak Symposium on Combinatorics, Prachatice 1990), pp. 141-143. Zbl 0767.05079, MR 1206256 |
| Reference:
|
[8] Kratochvíl J., Tuza Zs.: Intersection dimensions of graph classes.Graphs and Combinatorics 10 (1994), 159-168. MR 1289974 |
| Reference:
|
[9] Nešetřil J., Rödl V.: Partitions of subgraphs.in: Recent Advances in Graphs Theory (ed. M. Fiedler), Academia, Prague, 1975, pp. 413-423. MR 0429655 |
| Reference:
|
[10] Nešetřil J., Rödl V.: Products of graphs and their apllications.in: Proceedings of the Kuratowski Conference, Lagow (eds. M. Borowiecki, J.W. Kennedy and M.M. Syslo), Lecture Notes in Mathematics (Springer Verlag) 1018 (1983), 151-160. MR 0730645 |
| Reference:
|
[11] Rödl V.: A generalization of Ramsey theorem.in: Graphs, Hypergraphs and Block Systems (eds. M. Borowiecki, Z. Skupien and L. Szamkolowicz), Zielona Gora, 1976, pp. 211-220. |
| Reference:
|
[12] Shearer J.B.: A note on circular dimension.Discrete Math. 29 (1980), 103. Zbl 0437.05049, MR 0553653 |
| Reference:
|
[13] Thomassen C.: Interval representations of planar graphs.J. Combin. Th. Ser. B 40 (1986), 9-20. Zbl 0595.05027, MR 0830590 |
| Reference:
|
[14] Trotter W.T.: A characterization of Roberts' inequality for boxicity.Discrete Math. 28 (1979), 303-314. MR 0548629 |
| . |
