Name
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 $${f, g : V(G) \\to \\mathbb{N}}$$ f , g : V ( G ) ¿ N . Then the question is whether there exists an orientation D of G such that each vertex $${v \\in V(G)}$$ v ¿ V ( G ) satisfies $${\\sum_{u \\in N_D^{+}(v)}g(u) \\leq f(v)}$$ ¿ u ¿ N D + ( v ) g ( u ) ≤ f ( v ) . On one hand, this problem can be solved in polynomial time if g(v) = 1 for every vertex $${v \\in V(G)}$$ v ¿ V ( G ) . 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 $${h : E(G) \\to \\mathbb{N}}$$ h : E ( G ) ¿ N and where we ask for an orientation D such that each vertex $${v \\in V(G)}$$ v ¿ V ( G ) satisfies $${\\sum_{e \\in E_D^{+}(v)}h(e) \\leq f(v)}$$ ¿ e ¿ E D + ( v ) h ( e ) ≤ f ( v ) , 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 $${d_{D}^{+}(v) \\leq d_G(v)-1}$$ d D + ( v ) ≤ d G ( v ) - 1 for every vertex $${v \\in V(G)}$$ v ¿ V ( G ) . |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00373-013-1382-0 | Graphs and Combinatorics |
Keywords | Field | DocType |
vertex weighted graphs,chromatic number,orientations,brooks' theorem,kernels,brooks theorem | Complete graph,Graph,Combinatorics,Vertex (geometry),Bipartite graph,Degree (graph theory),Brooks' theorem,New digraph reconstruction conjecture,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 1 | 1435-5914 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Stiebitz | 1 | 207 | 30.08 |
| Zsolt Tuza | 2 | 1889 | 262.52 |
| Margit Voigt | 3 | 314 | 39.78 |