Weight choosability of graphs
Weight choosability of graphs
复制标题
DOI：
10.1002/jgt.20354
复制
发表时间：
2009-03
影响因子：
0.9
通讯作者：
Tomasz Bartnicki;J. Grytczuk;Stanislaw Niwczyk
中科院分区：
文献类型：
--
作者：
Tomasz Bartnicki;J. Grytczuk;Stanislaw Niwczyk
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
