Total weight choosability of graphs: towards the 1-2-3-conjecture
type: Item
instance of: scholarly article
title: Total weight choosability of graphs: towards the 1-2-3-conjecture
zbMATH Open document ID: 1468.05103
author: Lu Cao
published in: Journal of Combinatorial Theory. Series B
publication date: 2021-06-18T00:00:00Z
review text: The 1-2-3 conjecture states that for every simple graph with no isolated edges (a ``nice'' graph), one can assign weights of 1, 2, or 3 to each edge in such a way that all adjacent pairs of vertices have different total weights of incident edges. Although the conjecture was posed by \textit{M. Karoński} et al. [J. Comb. Theory, Ser. B 91, No. 1, 151--157 (2004; Zbl 1042.05045)], the best known result along these lines is that one can always succeed if weights of 4 or 5 are also permitted, due to \textit{M. Kalkowski} et al. [J. Comb. Theory, Ser. B 100, No. 3, 347--349 (2010; Zbl 1209.05087)]. This paper makes progress on a stronger conjecture about ``total weight \((a,b)\)-choosability''. A simple graph \((V, E)\) is said to be total weight \((a,b)\)-choosable if, given an \(a\)-element set of real numbers \(S_v\) for each vertex \(v\in V\) and a \(b\)-element set of real numbers \(S_e\) for each edge \(e\), it is possible to choose a weight \(w(x)\in S_x\) for each \(x\in V\cup E\) such that no two adjacent vertices share the same total weight (their own weight plus the weights of their incident edges). The total-weight-\((1,3)\) conjecture due to \textit{T.-L. Wong} and \textit{X. Zhu} [J. Graph Theory 66, No. 3, 198--212 (2011; Zbl 1228.05161)] states that every nice graph is total weight \((1,3)\)-chooseable. The total-weight-\((1,3)\) conjecture implies the 1-2-3 conjecture as a special case, by setting \(S_v = \{0\}\) for each vertex \(v\) and \(S_e = \{1,2,3\}\) for each edge \(e\). This paper is the first to prove a theorem of the form ``Every nice graph is total weight \((1,b)\)-choosable'' for a constant \(b\), namely, \(b=17\). It does so by proving an even stronger property, that every nice graph is algebraic total weight \((1,17)\)-choosable, using the combinatorial Nullstellensatz due to \textit{N. Alon} [Comb. Probab. Comput. 8, No. 1--2, 7--29 (1999; Zbl 0920.05026)]. The paper also concludes with several results about classes of graphs that are tot…
reviewed by: Owen Biesel
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 13F20
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 7360919
zbMATH Keywords: 1-2-3 conjecture
zbMATH Keywords: total weight choosablilty
zbMATH Keywords: combinatorial nullstellensatz
zbMATH Keywords: inner product
MaRDI profile type: Publication
full work available at URL: j.jctb.2021.01.008
OpenAlex ID: W3127740257
cites work: Combinatorial Nullstellensatz
cites work: A nowhere-zero point in linear mappings
cites work: Weight choosability of graphs
cites work: Total Weight Choosability of Trees
cites work: Q4947393
cites work: Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
cites work: Edge weights and vertex colours
cites work: Total weight choosability of graphs
cites work: Q3060867
cites work: Every graph is \((2,3)\)-choosable
DOI: 10.1016/J.JCTB.2021.01.008
Recommended article: Every nice graph is (1,5)-choosable
Recommended article: Every graph is \((2,3)\)-choosable
Recommended article: A NOTE ON EDGE WEIGHT CHOOSABILITY OF GRAPHS
Recommended article: Total weight choosability of graphs
Recommended article: An improved upper bound on edge weight choosability of graphs
Recommended article: Weight choosability of graphs
Recommended article: On total weight choosability of graphs
Recommended article: Bounding the monomial index and \((1,l)\)-weight choosability of a graph
Recommended article: Edge weights and vertex colours
Recommended article: Total weight choosability for Halin graphs
description: scientific article; zbMATH DE number 7360919