کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427264 | 686479 | 2012 | 4 صفحه PDF | دانلود رایگان |
Let D be a simple directed graph. Suppose that each edge of D is assigned with some number of chips. For a vertex v of D, let q+(v) and q−(v) be the total number of chips lying on the arcs outgoing form v and incoming to v, respectively. Let q(v)=q+(v)−q−(v). We prove that there is always a chip arrangement, with one or two chips per edge, such that q(v) is a proper coloring of D. We also show that every undirected graph G can be oriented so that adjacent vertices have different balanced degrees (or even different in-degrees). The arguments are based on peculiar chip shifting operation which provides efficient algorithms for obtaining the desired chip configurations. We also investigate modular versions of these problems. We prove that every k-colorable digraph has a coloring chip configuration modulo k or k+1.
Journal: Information Processing Letters - Volume 112, Issues 1–2, 15 January 2012, Pages 1-4