zbMATH — the first resource for mathematics

Total weight choosability of graphs. (English) Zbl 1228.05161
A graph $$G= (V, E)$$ is called $$(k, k')$$-total weight choosable if the following holds: For any mapping $$L$$ which assigns to each vertex $$x$$ a set $$L(x)$$ of $$k$$ real numbers, and assigns to each edge $$e$$ a set $$L(e)$$ of $$k'$$ real numbers, there is a mapping $$f: V\cup E\to\mathbb{R}$$ such that $$f(y)\in L(y)$$ for any $$y\in V\cup E$$ and for any two adjacent vertices $$x$$, $$x'$$, $\sum_{e\in E(x)} f(e)+ f(x)\neq \sum_{c\in E(x')} f(e)+ f(x').$ Complete graphs, complete bipartite graphs and trees other than $$K_2$$ are $$(1,3)$$-total weight choosable. The authors conjecture that every graph is $$(2,2)$$-total weight choosable and every graphs without isolated vertices is $$(1,3)$$-total weight choosable. The authors prove that for any graph $$H$$, a graph $$G$$ obtained from $$H$$ by subdividing each edge with at least two vertices is $$(2, 2)$$-total weight choosable.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 05C22 Signed and weighted graphs
Keywords:
total weight choosable
Full Text:
References:
 [1] Addario-Berry, Vertex coloring edge partitions, J Combin Theory Ser B 94 pp 237– (2005) · Zbl 1074.05031 · doi:10.1016/j.jctb.2005.01.001 [2] Addario-Berry, Electron Notes Discrete Math, in: Proceedings of GRACO2005 pp 257– (2005) [3] Addario-Berry, Vertex-coloring edge-weightings, Combinatorica 27 pp 1– (2007) · Zbl 1127.05034 · doi:10.1007/s00493-007-0041-6 [4] Alon, Combinatorial Nullstellensatz, Combin Prob. Comput 8 pp 7– (1999) · Zbl 0920.05026 · doi:10.1017/S0963548398003411 [5] Alon, A nowhere zero point in linear mappings, Combinatorica 9 pp 393– (1989) · Zbl 0717.05021 · doi:10.1007/BF02125351 [6] Alon, Colorings and orientations of graphs, Combinatorica 12 pp 125– (1992) · Zbl 0756.05049 · doi:10.1007/BF01204715 [7] Bartnicki, Weight choosability of graphs, J Graph Theory 60 pp 242– (2009) · Zbl 1210.05138 · doi:10.1002/jgt.20354 [8] Karoński, Edge weights and vertex colors, J Combin Theory Ser B 91 pp 151– (2004) · Zbl 1042.05045 · doi:10.1016/j.jctb.2003.12.001 [9] Kalkowski, Vertex-coloring edge-weightings: Towards the 1-2-3- Conjecture, J Combin Theory Ser B 100 pp 347– (2010) · Zbl 1209.05087 · doi:10.1016/j.jctb.2009.06.002 [10] J. Przybyło M. Woźniak www.ii.uj.edu.pl/preMD/ [11] J. Przybyło M. Woźniak www.ii.uj.edu.pl/preMD/ [12] Wang, A note on vertex-coloring 13-edge-weighting, Frontier Math 4 in China 3 pp 1– (2008) [13] T. Wong D. Yang X. Zhu Total weighting of graphs by max-min method, to appear in a volume dedicated to Lovász’s 60th birthday 2009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.