Oriented trees via chromatic number.

Resumen: It is folklore that every graph G contains every tree T whose order is at most \chi(G), the chromatic number of G.

This is no longer necessarily true if G and T are oriented. In 1980, Burr conjectured that an arbitrary orientation of a graph G contains every oriented tree of order 1 + \chi(G)/2.
We will present related questions and recent advances relating to this conjecture.

Posted on Apr 23, 2021 in Seminario de Grafos, Seminars