Orientations of Graphs with Prescribed Weighted Out-Degrees

Stiebitz, M. and Tuza, Zsolt and Voigt, M. (2015) Orientations of Graphs with Prescribed Weighted Out-Degrees. GRAPHS AND COMBINATORICS, 31 (1). pp. 265-280. ISSN 0911-0119

Text art_10.1007_s00373-013-1382-0.pdf Restricted to Registered users only Download (276kB) | Request a copy

Abstract

If we want to apply Galvin's kernel method to show that a graph G satisfies a certain coloring property, we have to find an appropriate orientation of G. This motivated us to investigate the complexity of the following orientation problem. The input is a graph G and two vertex functions {Mathematical expression}. Then the question is whether there exists an orientation D of G such that each vertex {Mathematical expression} satisfies {Mathematical expression}. On one hand, this problem can be solved in polynomial time if g(v) = 1 for every vertex {Mathematical expression}. On the other hand, as proved in this paper, the problem is NP-complete even if we restrict it to graphs which are bipartite, planar and of maximum degree at most 3 and to functions f, g where the permitted values are 1 and 2, only. We also show that the analogous problem, where we replace g by an edge function {Mathematical expression} and where we ask for an orientation D such that each vertex {Mathematical expression} satisfies {Mathematical expression}, is NP-complete, too. Furthermore, we prove some new results related to the (f, g)-choosability problem, or in our terminology, to the list-coloring problem of weighted graphs. In particular, we use Galvin's theorem to prove a generalization of Brooks's theorem for weighted graphs. We show that if a connected graph G has a block which is neither a complete graph nor an odd cycle, then G has a kernel perfect super-orientation D such that {Mathematical expression} for every vertex {Mathematical expression}. © 2013 Springer Japan.

Actions (login required)

Edit Item