COVERING 3-EDGE-COLORED RANDOM GRAPHS WITH MONOCHROMATIC TREES

Kohayakawa Yoshiharu; Mendonca Walner; Mota Guilherme Oliveira; Schuelke Bjarne

首页> 外文期刊>SIAM Journal on Discrete Mathematics >COVERING 3-EDGE-COLORED RANDOM GRAPHS WITH MONOCHROMATIC TREES

【24h】

COVERING 3-EDGE-COLORED RANDOM GRAPHS WITH MONOCHROMATIC TREES

机译：用单色树木覆盖3埃边色随机图

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices of an edge-colored random graph. More precisely, we show that for p n(-1/6)(ln n)(1/6), in any 3-edge coloring of the random graph G(n, p) we can find three monochromatic trees such that their union covers all vertices. This improves, for three colors, a result of Bucic, Korandi, and Sudakov.

机译：我们调查确定需要多种单色树木以覆盖边缘色随机图的顶点的问题。更准确地说，我们表明P＆GT;＆ n（-1/6）（ln n）（1/6），在随机图g（n，p）的任何3边缘着色中，我们可以找到三棵单色树，使其联盟涵盖所有顶点。这是三种颜色的改善，这是Bucic，Korandi和Sudakov的结果。

著录项

来源
《SIAM Journal on Discrete Mathematics》 |2021年第2期|1447-1459|共13页
作者
Kohayakawa Yoshiharu; Mendonca Walner; Mota Guilherme Oliveira; Schuelke Bjarne;
展开▼
作者单位

Univ Sao Paulo Inst Matemat & Estat BR-05508900 Sao Paulo SP Brazil;

Univ Warwick Math Inst Coventry CV4 7AL W Midlands England;

Univ Sao Paulo Inst Matemat & Estat BR-05508900 Sao Paulo SP Brazil;

Univ Hamburg Fachbereich Math D-20146 Hamburg Germany;

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类
关键词
graph partitioning; monochromatic trees; random graphs;

机译：图分隔;单色树木;随机图;

相似文献

外文文献
中文文献
专利

1. Covering 3-coloured random graphs with monochromatic trees [J] . Yoshiharu Kohayakawa, Walner Mendon?a, Guilherme Mota, Acta Mathematica Universitatis Comenianae . 2019,第3期

机译：用单色树木覆盖3种色的随机图
2. Monochromatic trees in random graphs [J] . YOSHIHARUKOHAYAKAWA, GUILHERME OLIVEIRAMOTA, MATHIASSCHACHT Mathematical Proceedings of the Cambridge Philosophical Society . 2019,第1期

机译：随机图中的单色树
3. Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles [J] . Allen P Combinatorics, probability & computing: CPC . 2008,第4期

机译：用两个不相交的单色循环覆盖两边彩色的完整图
4. Covering minimum spanning trees of random subgraphs [C] . Michel X. Goemans, Jan Vondrak Annual ACM-SIAM symposium on Discrete algorithms;ACM-SIAM symposium on Discrete algorithms . 2004

机译：覆盖随机子图的最小生成树
5. Covering trees: New variational bounds for map estimation in Markov random fields. [D] . Yarkony, Julian. 2010

机译：覆盖树木：马尔可夫随机场中地图估计的新变分界线。
6. Graph limits of random graphs from a subset of connected k‐trees [O] . Michael Drmota, Emma Yu Jin, Benedikt Stufler -1

机译：来自连接的k树的子集的随机图的图限制
7. Partitioning 3-Edge-Colored Complete Equi-Bipartite Graphs by Monochromatic Trees under a Color Degree Condition [O] . Xueliang Li, Fengxia Liu 2008

机译：在色度条件下通过单色树分隔3边缘彩色的完整平等图。

COVERING 3-EDGE-COLORED RANDOM GRAPHS WITH MONOCHROMATIC TREES

摘要

著录项

相似文献

相关主题

期刊订阅