Scholarlink

In 1980, Burr conjectured that every directed graph with chromatic number \(2k-2\) contains any oriented tree of order k as a subgraph. Burr showed that chromatic number \((k-1)^2\) suffices, which was improved in 2013 to \(\frac{k^2}{2} - \frac{k}{2} + 1\) by Addario-Berry et al. We give the first subquadratic bound for Burr’s conjecture, by showing that every directed graph with chromatic number \(8\sqrt{\frac{2}{15}} k \sqrt{k} + O(k)\) contains any oriented tree of order k. Moreover, we provide improved bounds of \(\sqrt{\frac{4}{3}} k \sqrt{k}+O(k)\) for arborescences, and \((b-1)(k-3)+3\) for paths on b blocks, with \(b\ge 2\) .

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

Oriented Trees in  \(O(k \sqrt{k})\) -Chromatic Digraphs, a Subquadratic Bound for Burr’s Conjecture

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Stéphane Bessy,
  • Daniel Gonçalves,
  • Amadeus Reinald

摘要

In 1980, Burr conjectured that every directed graph with chromatic number \(2k-2\) contains any oriented tree of order k as a subgraph. Burr showed that chromatic number \((k-1)^2\) suffices, which was improved in 2013 to \(\frac{k^2}{2} - \frac{k}{2} + 1\) by Addario-Berry et al. We give the first subquadratic bound for Burr’s conjecture, by showing that every directed graph with chromatic number \(8\sqrt{\frac{2}{15}} k \sqrt{k} + O(k)\) contains any oriented tree of order k. Moreover, we provide improved bounds of \(\sqrt{\frac{4}{3}} k \sqrt{k}+O(k)\) for arborescences, and \((b-1)(k-3)+3\) for paths on b blocks, with \(b\ge 2\) .