Equitable colorings of nonuniform hypergraphs

被引:0
作者
I. R. Shirgazina
机构
[1] Lomonosov Moscow State University,
来源
Mathematical Notes | 2016年 / 99卷
关键词
hypergraph; equitable coloring; simple hypergraph;
D O I
暂无
中图分类号
学科分类号
摘要
The well-known extremal problem on hypergraph colorings is studied. We investigate whether it is possible to color a hypergraph with a fixed number of colors equitably, i.e., so that, on the one hand, no edge is monochromatic and, on the other hand, the cardinalities of the color classes are almost the same. It is proved that if H = (V,E) is a simple hypergraph in which the least cardinality of an edge equals k, |V| = n, r|n, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum\limits_{e \in E} {{r^{1 - \left| e \right|}}} \leqslant c\sqrt k ,$$\end{document} where c > 0 is an absolute constant, then there exists an equitable r-coloring of H.
引用
收藏
页码:444 / 456
页数:12
相关论文
共 10 条
[1]  
Erdős P.(1961)On a property of families of sets ActaMath. Acad. Sci. Hungar 12 87-123
[2]  
Hajnal A.(1963)On a combinatorial problem NordiskMatematisk Tidsskrift 11 5-10
[3]  
Erdős P.(1964)On a combinatorial problem. II ActaMath. Acad. Sci. Hungar 15 445-447
[4]  
Erdős P.(2011)The Erdős–Hajnal problem of hypergraph colouring, its generalizations, and related problems UspekhiMat. Nauk 66 109-182
[5]  
Raigorodskii A. M.(1978)On 3-chromatic hypergraphs DiscreteMath. 24 127-137
[6]  
Shabanov D. A.(2015)Around Erdős–Lovász problemon colorings of non-uniform hypergraphs DiscreteMath. 338 1976-1981
[7]  
Beck J.(2014)Coloring non-uniform hypergraphs without short cycles Graphs Combin. 30 1249-1260
[8]  
Shabanov D. A.(2015)Equitable two-colorings of uniform hypergraphs European J. Combin. 43 185-203
[9]  
Shabanov D. A.(undefined)undefined undefined undefined undefined-undefined
[10]  
Shabanov D. A.(undefined)undefined undefined undefined undefined-undefined