main-content

## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

20.10.2015 | Ausgabe 1/2017 Open Access # Graphs with multiplicative vertex-coloring 2-edge-weightings

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

## Abstract

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 {\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.

Literatur
Über diesen Artikel

### Weitere Artikel der Ausgabe 1/2017 Zur Ausgabe