We consider arc colourings of oriented graphs such that for each vertex the colours of all out-arcs incident with the vertex and the colours of all in-arcs incident with the vertex form intervals. We prove that the existence of such a colouring is an NP-complete problem. We give the solution of the problem for r-regular oriented graphs, transitive tournaments, oriented graphs with small maximum degree, oriented graphs with small order and some other classes of oriented graphs. We state the conjecture that for each graph there exists a consecutive colourable orientation and confirm the conjecture for complete graphs, 2-degenerate graphs, planar graphs with girth at least 8, and bipartite graphs with arboricity at most two that include all planar bipartite graphs. Additionally, we prove that the conjecture is true for all perfect consecutively colourable graphs and for all forbidden graphs for the class of perfect consecutively colourable graphs.
Let \(\mathcal{D}_d\) be the class of d-degenerate graphs and let L be a list assignment for a graph G. A colouring of G such that every vertex receives a colour from its list and the subgraph induced by vertices coloured with one color is a d-degenerate graph is called the \((L,\mathcal{D}_d)\)-colouring of G. For a k-uniform list assignment L and \(d\in \mathbb {N}_0\), a graph G is equitably \((L,\mathcal{D}_d)\)-colorable if there is an \((L,\mathcal{D}_d)\)-colouring of G such that the size of any colour class does not exceed \(\left\lceil |V(G)|/k\right\rceil \). An equitable \((L,\mathcal{D}_d)\)-colouring is a generalization of an equitable list coloring, introduced by Kostochka et al., and an equitable list arboricity presented by Zhang. Such a model can be useful in the network decomposition where some structural properties on subnets are imposed. In this paper we give a polynomial-time algorithm that for a given (k, d)-partition of G with a t-uniform list assignment L and \(t\ge k\), returns its equitable \((L,\mathcal {D}_{d-1})\)-colouring. In addition, we show that 3-dimensional grids are equitably \((L,\mathcal {D}_1)\)-colorable for any t-uniform list assignment L where \(t\ge 3\).