Sandwich problems on orientations

摘要

The graph sandwich problem for property Π is defined as follows: Given two graphs G ~(1)=( V , E ~(1)) and G ~(2)=( V , E ~(2)) such that E ~(1)? E ~(2), is there a graph G =( V , E ) such that E ~(1)? E ? E ~(2)which satisfies property Π? We propose to study sandwich problems for properties Π concerning orientations, such as Eulerian orientation of a mixed graph and orientation with given in-degrees of a graph. We present a characterization and a polynomial-time algorithm for solving the m -orientation sandwich problem.