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 deg≥6 vertices; nice bipartite graphs admit a 6-weighting for deg≥2 vertices.
The 1-2-3 Conjecture and related problems: a survey
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
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.
verdicts
UNVERDICTED 2representative citing papers
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.
citing papers explorer
-
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 deg≥6 vertices; nice bipartite graphs admit a 6-weighting for deg≥2 vertices.
-
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.