Weight choosability of graphs |
| |
| Authors: | Tomasz Bartnicki Jarosław Grytczuk Stanisław Niwczyk |
| |
| Affiliation: | 1. Faculty of Mathematics, Computer Science, and Econometrics, University of Zielona Góra, 65‐516 Zielona Góra, Poland;2. Faculty of Mathematics and Computer Science, Theoretical Computer Science Department, Jagiellonian University, 30‐387 Kraków, Poland |
| |
| Abstract: | Suppose the edges of a graph G are assigned 3‐element lists of real weights. Is it possible to choose a weight for each edge from its list so that the sums of weights around adjacent vertices were different? We prove that the answer is positive for several classes of graphs, including complete graphs, complete bipartite graphs, and trees (except K2). The argument is algebraic and uses permanents of matrices and Combinatorial Nullstellensatz. We also consider a directed version of the problem. We prove by an elementary argument that for digraphs the answer to the above question is positive even with lists of size two. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 242–256, 2009 |
| |
| Keywords: | weight choosability monomial index of a graph permanent of a matrix |
|
|
