On hypergraph cliques with chromatic number 3 and a given number of vertices
Автор: Cherkashin D.D., Kulikov A.B., Raigorodskii A.M.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Раскраски гиперграфов
Статья в выпуске: 1 (13) т.4, 2012 года.
Бесплатный доступ
In 1973, P. Erdos and L. Lovasz pointed out that any hypergraph with pairwise intersecting edges has chromatic number 2 or 3. In the first case, this hypergraph can have any number of edges. However, Erdos and Lovasz proved that in the second case, the number of edges is bounded from above. For example, if a hypergraph is n-uniform, has pairwise intersecting edges and chromatic number 3, the number of its edges is less than nn. Recently, D.D. Cherkashin improved this bound (see [2]). In this paper, we further improve it, when the number of vertices of an n-uniform hypergraph is bounded from above by the value nm with some m = m(n).
Hypergraph clique, chromatic number
Короткий адрес: https://sciup.org/142185805
IDR: 142185805
Список литературы On hypergraph cliques with chromatic number 3 and a given number of vertices
- L. Babai, P. Frankl. Linear algebra methods in combinatorics. Part 1. -Department of Computer Science, The University of Chicago, Preliminary version 2, September 1992.
- D.D.Cherkashin. On hypergraph cliques with chromatic number 3//Moscow J. of Combinatorics and Number Th. -2011. -V. 1. -N. 3. -P. 3-11.
- P. Erdos, L. Lovasz. Problems and results on 3-chromatic hypergraphs and some related questions//Infinite and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai, North Holland. -1975. -V. 10. -P. 609-627.
- P. Frankl, K.Ota, N. Tokushige. Covers in uniform intersecting families and a counterexample to a conjecture of Lovasz//Journal of Combin. Th., Ser. A. -1996. -V. 74. -P. 33-42.
- T. Jensen, B.Toft. Graph coloring problems. -New York: Wiley Interscience, 1995.
- L. Lovasz. On minimax theorems of combinatorics//Math. Lapok. -1975. -V. 26. -P. 209-264 (in Hungarian).
- A.M. Raigorodskii. The linear algebra method in combinatorics. -Moscow Centre for Continuous Mathematical Education (MCCME), Moscow, Russia, 2007 (book in Russian).
- D.K.Ray-Chaudhury, R.M.Wilson. On t-designs//Osaka J. Math. -1975. -V. 12. -P. 735-744.