Interval colourable orientations of graphs (Q6589119)

It is well known that the problem of deciding whether a graph or an oriented graph is interval colorable is NP-complete. However, certain classes of graphs and oriented graphs can indeed admit interval colorings.\N\NIn this paper, the authors study the existence of interval colorable orientations of graphs.\N\NThe following is one of the main results of the paper.\N\NTheorem. If \(E^{\prime}\) is a set of edges of a graph \(G\) such that there exists an interval colourable orientation of the graph \(G-E^{\prime}\) and if each edge in \(E^{\prime}\) has at least one end-vertex of degree not greater than two in \(G\), then there exists an orientation of the graph \(G\) that is interval colourable.\N\NAs a consequence of this result, for every graph \(G\), there exists an orientation of the graph \(S(G)\) that is interval colorable.\N\NAnother notable result is the following.\N\NTheorem. Let \(G\) be a graph that is decomposable into graphs \(G_1\) and \(G_2\), where \(G_1\) is an interval colorable bipartite graph and each connected component of \(G_2\) has at most one cycle that, if it exists, is of odd length. Then there exists an orientation \(D\) of \(G\) that is interval colorable.\N\NIt is also proved that cactus graphs, graphs homeomorphic to Halin graphs, and full subdivision graphs have interval colorable orientations.\N\NIn Theorem 4.3, the authors confirm the existence of interval colorable orientations for some \(k\)-trees. As a consequence of this theorem, it follows that all \(k\)-paths with natural \(k\), and also all \(k\)-trees with the maximum degree at most 2k, where \(k \in \{1, 2, 3, 4\}\), possess interval colorable orientations.\N\NThe following open problems are mentioned at the end of the paper.\N\N\begin{itemize}\N\item[1.] What is the relationship between the existence of an interval colorable orientation of a graph \( G \) and the statement \( \theta_{\text{int}}(G) \leq 2 \) within the class of non-bipartite graphs?\N\item[2.] Under which necessary and sufficient conditions does a non-bipartite graph \( G \) have an orientation \( D \) such that \( G^*(D) \) is a forest?\N\item[3.] How can one recognize and calculate the number of closed trails of even length in a graph?\N\item[4.] Is it true that for each \( k \)-tree, where \( k \geq 2 \), there exists an interval colorable orientation?\N\end{itemize}