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.
Еще
Статья научная