Oriented trees in digraphs
Oriented trees in digraphs
复制标题
有向图中的有向树
DOI：
10.1016/j.disc.2013.01.011
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Stéphan Thomassé
中科院分区：
文献类型：
--
作者：
L. Addario;F. Havet;C. Sales;B. Reed;Stéphan Thomassé
设f（k）是使得每个f（k）-色有向图包含k阶定向树的最小整数。Burr一般地证明了f（k）≤（k−1）2，并证明了f（k）=2k−2。Burr还证明了每个（8 k −7）-色有向图包含每个反向树。我们改进了Burr的两个界。我们证明了f（k）≤k2/2−k/2+1，并且每个k阶反向树包含在每个（5 k −9）-色有向图中。我们做了一个猜想，解释了为什么反向树更容易处理。它指出，如果|E（D）|>（k−2）|V（D）|，则有向图D包含每一个k阶反向树。这是一个共同的加强伯尔的猜想的反向树和著名的Erdens-Sós猜想。我们的猜想对于一般树的类比是错误的，不管用什么函数f（k）来代替k−2。证明了直径为3的反向树的猜想，并给出了其它一些证明.沿着这条路，我们证明了每一个无圈k-色有向图都包含每一个k阶定向树，并提出了进一步发展Burr猜想的一些方法.
Let f(k) be the smallest integer such that every f(k)-chromatic digraph contains every oriented tree of order k. Burr proved f(k)≤(k−1)2in general, and he conjectured f(k)=2k−2. Burr also proved that every (8k−7)-chromatic digraph contains every antidirected tree. We improve both of Burr’s bounds. We show that f(k)≤k2/2−k/2+1 and that every antidirected tree of order k is contained in every (5k−9)-chromatic digraph. We make a conjecture that explains why antidirected trees are easier to handle. It states that if |E(D)|>(k−2)|V(D)|, then the digraph D contains every antidirected tree of order k. This is a common strengthening of both Burr’s conjecture for antidirected trees and the celebrated Erdős-Sós Conjecture. The analogue of our conjecture for general trees is false, no matter what function f(k) is used in place of k−2. We prove our conjecture for antidirected trees of diameter 3 and present some other evidence for it. Along the way, we show that every acyclic k-chromatic digraph contains every oriented tree of order k and suggest a number of approaches for making further progress on Burr’s conjecture.