- Project Year:
2023
- REU Student (s):
Barbora Dohnalova | Charles University (Prague, Czech Republic)
| Jiri Kalvoda | Charles University (Prague, Czech Republic)
- Student 1 Institution:
Charles University (Prague, Czech Republic)
- Student 2 Institution:
Charles University (Prague, Czech Republic)
- Project Mentor:
Sophie Spirkl
- Project Mentor Area:
Department of Combinatorics and Optimization, University of Waterloo
- Project Abstract:
In this article, we study the problem of classifying graphs that admit `KT orientations'. A~directed graph $G$ is said to have a KT orientation if there is at most one directed path between any pair of vertices of $G$. We extend the known examples of classes of graphs that admit a KT orientation and those graph families which do not. We show that the problem of determining whether a given graph admits a KT orientation is NP-complete, in particular this also applies if we restrict ourselves to planar graphs. Moreover we provide an algorithm to decide if a digraph with max-degree at most 3 has a KT orientation, while for graphs with max-degree $4$, this remains NP-complete. Finally we construct a graph family with small independence number (sub-linear in the number of vertices), and thus has unbounded fractional chromatic number, that admits a KT orientation.
