2018/06/09 by Király, Zoltán, Pálvölgyi, Dömötör · 2 citations
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1806.03426
In this note we study the complexity of some generalizations of the notion of st-numbering. Suppose that given some functions f and g, we want to order the vertices of a graph such that every vertex v is preceded by at least f(v) of its neighbors and succeeded by at least g(v) of its neighbors. We prove that this problem is solvable in polynomial time if fg≡ 0, but it becomes NP-complete for f≡ g ≡ 2. This answers a question of the first author posed in 2009.