The 1-2-3 Conjecture and related problems: a survey
read the original abstract
The 1-2-3 Conjecture, posed in 2004 by Karonski, Luczak, and Thomason, is as follows: "If G is a graph with no connected component having exactly 2 vertices, then the edges of G may be assigned weights from the set {1,2,3} so that, for any adjacent vertices u and v, the sum of weights of edges incident to u differs from the sum of weights of edges incident to v." This survey paper presents the current state of research on the 1-2-3 Conjecture and the many variants that have been proposed in its short but active history.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
The Parameterized Complexity of Vertex-Coloring Edge-Weighting
Vertex-Coloring {0,1}-Edge-Weighting is W[1]-hard parameterized by feedback vertex set size, FPT by vertex cover size (with a restriction for the pre-weighted variant), and admits XP algorithms parameterized by treewidth.
-
Neighbour sum distinguishing edge-weightings with local constraints
Every nice graph (no K2 components) with Δ≤5 admits a neighbour-sum-distinguishing (Δ+2)-edge-weighting where deg≥2 vertices have at least two distinct incident weights; every nice graph admits such a 7-weighting for ...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.