REU Project
- KT Orientation in Graphs
- Project Year: 2023
- REU Student (s): Barbora Dohnalova | Charles University (Prague, Czech Republic) | Gaurav Kucheriya | Charles University (Prague, Czech Republic)
- Project Mentor (s) : Sophie Spirkl - 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.