Originator(s): Chandra Chekuri, Alina Ene, Nitish Korula (presented by Alina Ene - REGS 2009)
We have a rooted tree T and an integer t(e) for each edge e of T called the threshold for e. We also have a family P of paths in T such that for each path in P, one endpoint is a descendent of the other. Each path P&isinP has an integer value v(p).
Definition: An edge e sees a path P in P if e lies on P and v(p)≥t(e). A subset S of P is k-feasible if each edge e in the tree sees at least k paths in S. We refer to 1-feasible sets simply as feasible sets. A valid coloring of P is a coloring of the paths in P such that each color class is a feasible set.
In general, we seek a valid coloring with as many color classes as possible.
Conjecture 1: There is a constant c such that whenever T is a rooted tree, and P is a k-feasible family of paths in T, there is a valid coloring of P with at least k/c color classes.
Theorem [CEK09+]: If T is a path and P is a k-feasible family of paths, then there is a valid coloring of P with at least k/2 color classes.
A broom is a rooted tree in which every non-leaf vertex has exactly one child except for the one vertex that is the parent of all the leaves.
Conjecture 2: There is a constant c such that whenever T is a broom, and P is a k-feasible family of paths in T, there is a valid coloring of P with at least k/c color classes.
Solution: Evan Vanderzee disproved Conjecture 2 (which disproves Conjecture 1 as well). He showed that, for any given k, there is a broom and a k-feasible family of paths on it that does not have a valid coloring with more than one color class. However, his broom having a k-feasible family with no valid 2-coloring has more than kk-1 vertices. In terms of the number of vertices, n, this k is about log n / log log n. The example shows that to guarantee valid colorings, k must be larger than that.
Question 3: Does there exist a function ƒ such that when k>ƒ(n), every k-feasible family of paths in any n-vertex rooted tree has a valid 2-coloring?
References:
[CEK09+]: Chandra Chekuri, Alina Ene, Nitish Korula. Unpublished work,
2009.