×

On the 1-2-3-conjecture. (English) Zbl 1310.05088

Summary: A \(k\)-edge-weighting of a graph \(G\) is a function \(w:E(G)\to \{1,\ldots ,k\}\). An edge-weighting naturally induces a vertex coloring \(c\), where for every vertex \(v\in V(G)\), \(c(v)=\sum _{e\sim v}w(e)\). If the induced coloring \(c\) is a proper vertex coloring, then \(w\) is called a vertex-coloring \(k\)-edge-weighting (VC \(k\)-EW). M. Karoński et al. [J. Comb. Theory, Ser. B 91, No. 1, 151–157 (2004; Zbl 1042.05045)] conjectured that every graph admits a VC 3-EW. This conjecture is known as the 1-2-3-conjecture.
In this paper, first, we study the vertex-coloring edge-weighting of the Cartesian product of graphs. We prove that if the 1-2-3-conjecture holds for two graphs \(G\) and \(H\), then it also holds for \(G\square H\). Also we prove that the Cartesian product of connected bipartite graphs admits a VC 2-EW. Moreover, we present several sufficient conditions for a graph to admit a VC 2-EW. Finally, we explore some bipartite graphs which do not admit a VC 2-EW.

MSC:

05C15 Coloring of graphs and hypergraphs
05C22 Signed and weighted graphs
05C76 Graph operations (line graphs, products, etc.)

Citations:

Zbl 1042.05045