Coloring chip configurations on graphs and digraphs

• Published in: Information processing letters 2012-01, Vol.112 (1), p.1-4
• Main Authors: Borowiecki, Mieczysław, Grytczuk, Jarosław, Pilśniak, Monika
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Algorithms; Applied sciences; Balancing; Chip formation; Chips; Coloring; Combinatorial problems; Combinatorics; Combinatorics. Ordered structures; Computer science; control theory; systems; Designs and configurations; Exact sciences and technology; Graph algorithms; Graph coloring; Graph theory; Graphs; Mathematics; Miscellaneous; Modular; Optimization algorithms; Sciences and techniques of general use; Studies; Theoretical computing
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2011.09.011

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 .