Skip to main content


Weitere Artikel dieser Ausgabe durch Wischen aufrufen

20.10.2015 | Ausgabe 1/2017 Open Access

Journal of Combinatorial Optimization 1/2017

Graphs with multiplicative vertex-coloring 2-edge-weightings

Journal of Combinatorial Optimization > Ausgabe 1/2017
Joanna Skowronek-Kaziów


A k-weighting w of a graph is an assignment of an integer weight \(w(e)\in \{1,...k\}\) to each edge e. Such an edge weighting induces a vertex coloring c defined by \(c(v)=\mathop {\displaystyle {\prod }}\limits _{v\in e}w(e).\) A k-weighting of a graph G is multiplicative vertex-coloring if the induced coloring c is proper, i.e., \(c(u)\ne c(v)\) for any edge \(uv\in E(G).\) This paper studies the parameter \(\mu (G),\) which is the minimum k for which G has a multiplicative vertex-coloring k-weighting. Chang, Lu, Wu, Yu investigated graphs with additive vertex-coloring 2-weightings (they considered sums instead of products of incident edge weights). In particular, they proved that 3-connected bipartite graphs, bipartite graphs with the minimum degree 1, and r-regular bipartite graphs with \(r\ge 3\) permit an additive vertex-coloring 2-weighting. In this paper, the multiplicative version of the problem is considered. It was shown in Skowronek-Kaziów (Inf Process Lett 112:191–194, 2012) that \(\mu (G)\le 4\) for every graph G. It was also proved that every 3-colorable graph admits a multiplicative vertex-coloring 3 -weighting. A natural problem to consider is whether every 2-colorable graph (i.e., a bipartite graph) has a multiplicative vertex-coloring 2-weighting. But the answer is no, since the cycle \(C_{6}\) and the path \(P_{6}\) do not admit a multiplicative vertex-coloring 2-weighting. The paper presents several classes of 2-colorable graphs for which \(\mu (G)=2\), including trees with at least two adjacent leaf edges, bipartite graphs with the minimum degree 3 and bipartite graphs \(G=(A,B,E)\) with even \(\left| A\right| \) or \(\left| B\right| \).

Unsere Produktempfehlungen

Premium-Abo der Gesellschaft für Informatik

Sie erhalten uneingeschränkten Vollzugriff auf alle acht Fachgebiete von Springer Professional und damit auf über 45.000 Fachbücher und ca. 300 Fachzeitschriften.

Über diesen Artikel

Weitere Artikel der Ausgabe 1/2017

Journal of Combinatorial Optimization 1/2017 Zur Ausgabe

Premium Partner