Bounds on Rainbow-Path-Free Vertex Colorings of Trees
Sharp extremal bounds for the maximum number of colors in a vertex coloring of a tree that avoids a rainbow path P_k (all vertices distinctly colored), in both the unrestricted (c_k) and proper (cp_k) settings. For trees of order n the minimum value of c_4 and cp_4 is (n+2)/2 -- with the trees attaining minimum c_4 being exactly the coronas -- and the minimum value of c_5 and cp_5 is (n+3)/2, attained exactly by the octopuses. Proofs go through the P_k-thwarting number theta_{P_k}(T), the fewest edges whose removal destroys every P_k, via the tree identity c_H(T) = n - theta_H(T), together with path formulas, attachment lemmas and a boring-vertex recoloring argument.
Bounds on Coloring Trees without Rainbow Paths Wayne Goddard, Tyler Herrman, Simon J. Hughes
For a vertex-colored graph, a rainbow subgraph is one whose vertices all receive distinct colors. Writing c_k(G) for the maximum number of colors in a (not necessarily proper) coloring of G with no r…