Modulo orientations with bounded out-degrees
Morteza Hasanvand · Discrete Mathematics · 2023
Let G be a graph, let k be a positive integer, and let p : V ( G ) → { − 1 , … , k − 2 } be a mapping with | E ( G ) | ≡ k ∑ v ∈ V ( G ) p ( v ) . In this paper, we show that if G is essentially ( 3 k − 3 ) -edge-connected and for each vertex v , d G ( v ) ≥ 2 k − 1 + p ( v ) , then G has an orientation such that for each vertex v , d G + ( v ) ≡ k p ( v ) , and ⌊ d G ( v ) 2 ⌋ − ( k − 1 ) ≤ d G + ( v ) ≤ ⌈ d G ( v ) 2 ⌉ + ( k − 1 ) . In addition, we show that if G can be decomposed into 2 k − 2 edge-disjoint spanning trees and a factor F having an orientation such that for each vertex v , d F + ( v ) ≥ l 0 ( v ) , then G has an orientation such that for each vertex v , d G + ( v ) ≡ k p ( v ) , and s ( v ) ≤ d G + ( v ) ≤ d G ( v ) − s 0 ( v ) , where s , s 0 , and l 0 are three integer-valued functions on V ( G ) satisfying s ( v ) + s 0 ( v ) + k − 1 ≤ d G ( v ) and max { s ( v ) , s 0 ( v ) } ≤ l 0 ( v ) + ( k − 1 ) for each vertex v , and max { s ( z ) , s 0 ( z ) } ≤ l 0 ( z ) for a vertex z .