Interval colourable orientations of graphs

DOI10.1016/J.DISC.2024.114143MaRDI QIDQ6589119zbMATH OpenFDO

Authors Marta Borowiecka-Olszewska, Ewa Drgas-Burchardt

Publication date 19 August 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2024.114143

zbMATH Keywords

consecutive colouring digraph interval colouring interval colouring thickness oriented graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Applications of graph theory (05C90)

Review text

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}

Recommendations

Cites work

Cited in

(1)

On interval colouring reorientation number of oriented graphs

This page was built for publication: Interval colourable orientations of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6589119)