On splittable colorings of graphs and hypergraphs
On splittable colorings of graphs and hypergraphs
复制标题
关于图和超图的可分割着色
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
R. Ramamurthi
中科院分区：
文献类型：
--
作者：
Z. Füredi;R. Ramamurthi
作为对完全图的推广，Erdos和Gyarfas[7]引入了完全图的分裂着色的概念。在这项工作中，我们通过与对手进行两轮比赛，将这种着色与经典的拉姆齐着色问题进行比较，提供了另一种解释。我们证明了在[7]的极值（r,m）分裂染色问题上所使用的技术和得到的界在本质上更接近图的图兰理论而不是拉姆齐理论。我们将这些着色的概念推广到超图中，并给出了上界和一些精确的结果。©2002 Wiley期刊公司[J] .图论学报（自然科学版），2002
The notion of a split coloring of a complete graph was introduced by Erdos and Gyarfas [7] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two-round game played against an adversary. We show that the techniques used and bounds obtained on the extremal (r,m)-split coloring problem of [7] are closer in nature to the Turan theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226237, 2002