Scholarlink

<p>It is known that every 2-edge-colored complete graph <i>K</i><sub><i>n</i></sub> (respectively, complete bipartite graph <i>K</i><sub><i>n,m</i></sub>) contains two monochromatic trees whose vertices cover all the vertices of <i>K</i><sub><i>n</i></sub> (respectively, <i>K</i><sub><i>n,m</i></sub>). A natural question is that what is the largest integer <i>t</i> such that the following statement holds: if <i>G</i> is obtained from the complete graph <i>K</i><sub><i>n</i></sub> (respectively, complete bipartite graph <i>K</i><sub><i>n,m</i></sub>) by deleting <i>t</i> edges arbitrarily, then every 2-edge-colored <i>G</i> still contains two monochromatic trees whose vertices cover all the vertices of <i>G</i>. In this paper, we show that we can delete at most <i>n</i> − 1 edges in the complete graph case, and at most one edge in the complete bipartite graph case. We also construct examples showing that both results are sharp. We in fact prove these results in much stronger forms, and we also obtain some analogous results for multipartite graphs. These results generalize a result on monochromatic path covers of Gyárfás, Jagota and Schelp from 1997.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Monochromatic Tree Covers in Nearly Complete (Bipartite) Graphs

  • 期刊论文

  • 发表日期：

    2025年12月8日

查看全文
  • Xi-he Li,
  • Zhi-hui Li,
  • Xiang-xiang Liu,
  • Li-gong Wang

摘要

It is known that every 2-edge-colored complete graph Kn (respectively, complete bipartite graph Kn,m) contains two monochromatic trees whose vertices cover all the vertices of Kn (respectively, Kn,m). A natural question is that what is the largest integer t such that the following statement holds: if G is obtained from the complete graph Kn (respectively, complete bipartite graph Kn,m) by deleting t edges arbitrarily, then every 2-edge-colored G still contains two monochromatic trees whose vertices cover all the vertices of G. In this paper, we show that we can delete at most n − 1 edges in the complete graph case, and at most one edge in the complete bipartite graph case. We also construct examples showing that both results are sharp. We in fact prove these results in much stronger forms, and we also obtain some analogous results for multipartite graphs. These results generalize a result on monochromatic path covers of Gyárfás, Jagota and Schelp from 1997.