Раскраски гиперграфов. Рубрика в журнале - Труды Московского физико-технического института
On hypergraph cliques with chromatic number 3 and a given number of vertices
Статья научная
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).
Бесплатно
Об одном обобщении задачи Эрдеша-Ловаса
Статья научная
Исследуется обобщение классической задачи Эрдеша-Ловаса, связанное с раскрасками неоднородных гиперграфов. Пусть H = (V,E) - произвольный гиперграф с минимальной мощностью ребра n и обхватом не меньше 4. В работе получено новое достаточное условие r-раскрашиваемости гиперграфа H в терминах ограничения на функцию fr(H) =∑eϵЕr1-ӀeӀ.
Бесплатно
Рекуррентные верхние оценки в задаче Эрдеша-Хайнала о раскраске гиперграфа и в ее обобщениях
Статья научная
В 1961 году П. Эрдеш и А. Хайнал поставили задачу об отыскании величины m(n), равной наименьшему количеству ребер в n-однородном гиперграфе с хроматическим числом больше двух. Сейчас известны различные асимптоти- ческие оценки для m(n). Однако точные значения найдены лишь при n ≤ 3. При других малых n есть только рекуррентные оценки. Мы рассматриваем важное обобщение задачи, а именно, нас интересует величина mk(n), рав- ная минимальному числу ребер в n-однородном гиперграфе, не допускающем двухцветной раскраски множества своих вершин, при которой каждое ребро содержит не менее k вершин первого цвета и не менее k вершин второго цвета. Нам удается найти ряд рекуррентных оценок для mk(n), которые при многих n и k значительно уточняют все ранее доказанные результаты.
Бесплатно
