LAUSR

Let D be any edge orientation of a graph G. We denote by $$\Delta _k(D)$$Δk(D) the maximum value t for which there exists a directed path $$v_1, \ldots , v_k$$v1,…,vk such that $$d^{out}(v_k)=t$$dout(vk)=t, where $$d^{out}(v_k)$$dout(vk) is the out-degree of $$v_k$$vk in D. We first obtain some bounds for the chromatic number of G in terms of $$\Delta _k(D)$$Δk(D) and then show a relationship between $$\Delta _k(D)$$Δk(D) and vertex partitions of a graph into degenerate subgraphs.